找出给定函数的时间复杂度

Question

对于给定的程序,时间复杂度将是多少.

int count = 0;

    for(int i = n; i > 0; i /= 2)
    {
        for(int j = 0; j < i; j++)
        {
            count++;
        }
    }

我的理解,应该是O(nlogn)因为i环是分而治之,因此O(logn)与j回路O(n).

但是,正确的答案是O(n).有人可以解释原因吗？

Answer 1

它是O(n):

外循环具有O(logn)迭代,因为i从n每次迭代开始并减半.

现在让我们考虑内循环的迭代次数:

• 在外循环的第一次迭代中,内循环具有n迭代(自i==n).

• 在外循环的第二次迭代中,内循环具有n/ 2次迭代(自i==n/2).

• ...

• log(n)在外循环的'th(和最后)迭代中,内循环有1次迭代(从i==1).

总结我们得到的所有内循环迭代:

n + n/2 + n/4 + ... + 1 <= 2*n = O(n)