Suppose $A$ is an $m\times n$ real matrix and we need to find $||A||_p$ for $p \notin \{1,2,\infty \}$. What is the most efficient way to compute $||A_p||$?

Here's one naive approach I can think of. Sample random points ||x|| on the unit hypersphere , computing $||Ax||_p$ for each such and take the maximum. What I would like to know is the runtime of this approach for the "average" A,and how we can optimize this for special classes of matrices( like Diagonal, Orthonormal, etc.)?