algorithm - 代码片段的复杂性第 2 部分

Question

根据输入大小给出以下代码片段的复杂度纽:

for(int i=0;i<n;i++) // n*
    for(int j =1;j<=n;j=j*2) // n/2 (its half n, but I assume it still counts as n, or is it log(n)?)
        a[i]=a[j-1]/2; // 1

for(int i=0;i-n;i++) // n*
    if(a[i] %2==0)  // 1*
        a[i]=2*a[i]; // 1

你从下往上开始。复杂度是:n^2 + n 还是 O(n^2)？

有什么地方可以让我了解如何计算简单算法的复杂性？

Answer 1

正如你所怀疑的，

for(int j =1;j<=n;j=j*2)

这是 O(logn)，因为每次迭代 j 都乘以 2。所以总时间是 O(nlogn)。

至于看哪里，我喜欢算法导论，但如果只是简单的算法分析，任何好的教科书都足够了。