algorithm - 作为 N 函数的增长顺序

Question

我正在练习复杂的算法，我认为下面的所有代码在增长阶数方面都是二次的，但由于我需要作为 N 的函数的增长阶数，我认为这会改变事情，但我不会确切地知道如何解决这个问题。

int sum = 0;
    for(int n = N; n > 0; n/=2)
    for(int i = 0; i < n; i++)
    sum++

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < i; j++)
    sum++

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < N; j++)
    sum++

Answer 1

int sum = 0;
    for(int n = N; n > 0; n/=2)
    for(int i = 0; i < n; i++)
    sum++

这是O(N)，内循环总共运行了N + N/2 + N/4 + ... + 1 次，这个总和收敛当 N->infinity 时为 2N，因此它是 O(N)。

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < i; j++)
    sum++

这与案例 1 非常相似，我将把它留给您作为练习。按照我在那里所做的相同方法，您将得到答案。

int sum = 0;
    for(int i = 1; i < N; i*=2)
    for(int j = 0; j < N; j++)
    sum++

这里，主要区别是内层循环不依赖于外层循环的变量。这意味着，无论 i 的值如何，内部循环都会重复 N 次。

因此，您需要了解外层循环将重复多少次，并将其乘以N。

在解释完这些准则后，我也将它留给您作为练习。