In this paper, by improving the computation efficiency (CE) and ensuring the fairness among users, we study the CE optimization for millimeter-wave mobile edge computing (mmWave-MEC) Networks with NOMA, where both the analog beamforming (ABF) and hybrid beamforming (HBF) architectures under the partial offloading mode are considered. Firstly, according to the max-min fairness criterion, the CE maximization problem is formulated to jointly optimize the ABF and the local resource allocation of each user. An efficient CE optimization algorithm based on the penalized successive convex approximation is proposed to solve this non-convex problem. Then, the max-min CE optimization problem in mmWave-MEC with HBF is studied, where the joint design of the HBF and the local resource allocation of each user is carried out. By using the penalty function and the inexact block coordinate descent method, a feasible CE optimization algorithm is developed to tackle this challenging problem. Simulation results verify the convergence of the proposed algorithms and show that the proposed computation-efficient resource allocation schemes can improve the CE effectively, and mmWave-MEC with HBF can obtain higher CE than that with ABF. Besides, the NOMA scheme exhibits superior performance over the conventional orthogonal multiple access scheme in terms of CE.