作为 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++

这个和case1非常相似，留给大家练习。按照我在那里做的同样的方法，你会得到答案。

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

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

所以，你需要知道外层循环会重复多少次，然后乘以N。

在解释完这些指南后，我也把它留给你作为练习。

作为 N 函数的增长顺序

Order of growth of as function of N

algorithm

big-o

time-complexity