随着N的增长，函数的增长顺序

Question

随着N的增长，函数的增长顺序

4

我正在练习算法复杂度，我认为以下所有代码在增长阶数方面都是二次的，但由于我需要将增长阶数表示为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++

- PRCube

不，它们不是二次的。最简单的方法是对N=10、N=100和N=1000进行运行，并观察总和的顺序。然后推理为什么是这样的。 - Gassa

我得出的结论是：1. 代码是对数的，2. 和 3. 是线性的。但是，我不能确定。 - PRCube

实际上，它们都不是二次的。 - amit

似乎是一个作业问题...第一种情况：外部循环大约进行log(N)次迭代，内部循环大约进行N、N/2、N/4、N/8...次迭代，因此最终的“sum”大约为2N。第二种情况：外部循环最多进行floor(log(N))次迭代，因此最终的总和不超过2N。最后一种情况留给你自己思考。 - CiaPan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

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。

我在解释了这些准则之后也让您自己练习。