We consider evaluation complexity of minimization problems with nonconvex, non-Lipschitz regularization terms. For $ L_2-L_p$ non-Lipschitz regularized minimization, we show that finding a global optimal solution is strongly NP-hard. We propose a smoothing quadratic regularization algorithm for unconstrained problems and a first-order interior point algorithm for a class of problems with box constraints. Both algorithms are easy to implement and the worst-case iteration complexity for finding an $\epsilon$ scaled first-order stationary point is $O(\epsilon^{-2})$. Moreover, we develop a second-order interior point algorithm using the Hessian matrix, and solve a quadratic program with a ball constraint at each iteration. Although the second-order interior point algorithm costs more computational time than that of the first-order algorithm in each iteration, its worst-case iteration complexity for finding an $\epsilon$ (scaled) second-order stationary point is reduced to $O(\epsilon^{-3/2})$. Examples are presented to illustrate the theory and algorithms.