如果题目允许优化程序的话，计算X的多次幂时可以保留中间结果，比如你已经有了X^3，计算X^4的时候就不用从头乘一遍，也不用二分着来，直接X^3在乘X就可以了。如果采用这样的策略，这题是可以以O(N)实现的。
如果不考虑上面所说，复杂度是NlogN，你的计算过程可行。另外也可估算，即单次求幂是logN，求N次就是NlogN，这样估出来的是上界。但是在不保留中间结果的算法下，是无法达成O（N）的，故可以不严谨地“直觉”知道下界也是NlogN。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024