这个算法的时间复杂度是如何计算出来的?

Question

2-11的这个程序就是b中所说的例程
这是我的想法: 2-11的复杂度是logN, 那么ai*X^i就是(1+log1) + (1+log2) + .... + (1+logN) = n + (log1 + log2 +... + logN) = n + log(1*2*3*..*n) = n + log(N!) . 然后根据斯特林公式 : . 复杂度= n + log((n/e)^n) = n + nlog(n/e) [前面的根号2πn太小了直接舍去] , 所以时间复杂度为nlogN.

不知道这么想对不对? 或者有什么更加标准化的计算复杂度的过程, 望指明.
拜托了!

Answer 1

如果题目允许优化程序的话，计算X的多次幂时可以保留中间结果，比如你已经有了X^3，计算X^4的时候就不用从头乘一遍，也不用二分着来，直接X^3在乘X就可以了。如果采用这样的策略，这题是可以以O(N)实现的。

如果不考虑上面所说，复杂度是NlogN，你的计算过程可行。另外也可估算，即单次求幂是logN，求N次就是NlogN，这样估出来的是上界。但是在不保留中间结果的算法下，是无法达成O（N）的，故可以不严谨地“直觉”知道下界也是NlogN。