我怎样才能在这个 while 循环中获得大 O 符号？

Question

计算成本只会考虑c = c+1;执行了多少次

我想用 n 表示大 O 表示法。

count = 0; index = 0; c = 0;
while (index <= n) {
   count = count + 1;
   index = index + count;
   c = c + 1;
}

我认为如果“计数的迭代”是k，“索引的迭代”是n，那么k(k+1)/2 = n。

所以，我认为 O(root(n)) 就是答案。

这个问题的答案是正确的吗？

Answer 1

让我们先看看index每次循环迭代是如何变化的：

index = 0 + 1 = 1
index = 0 + 1 + 2 = 3
index = 0 + 1 + 2 + 3 = 6
...
index = 0 + 1 + ... + i-1 + i = O(i^2)

然后我们需要计算循环运行了多少次，相当于在等式中隔离i：

i^2 = n =>
i = sqrt(n)

所以你的算法运行在 O(sqrt(n)) 也可以写成 O(n^0.5).

Answer 2

Is that right solution about this question?

这很容易测试。 while 循环结束时 c 的值将是循环运行的次数（因此， c = c + 1; 语句的执行次数).因此，让我们检查 c 的值，对于各种 n，看看它们与假定的 O(√n) 复杂性有何不同：

#include <stdio.h>
#include <math.h>

int main()
{
    printf("    c   root(n)  ratio\n"); // rubric
    for (int i = 1; i < 10; ++i) {
        int n = 10000000 * i;
        int count = 0;
        int index = 0;
        int c = 0;
        while (index < n) {
            count = count + 1;
            index = index + count;
            c = c + 1;
        }
        double d = sqrt(n);
        printf("%5d  %8.3lf %8.5lf\n", c, d, c / d);
    }
    return 0;
}

输出：

    c   root(n)  ratio
 4472  3162.278  1.41417
 6325  4472.136  1.41431
 7746  5477.226  1.41422
 8944  6324.555  1.41417
10000  7071.068  1.41421
10954  7745.967  1.41416
11832  8366.600  1.41419
12649  8944.272  1.41420
13416  9486.833  1.41417

我们可以看到，尽管有一些 'rounding' 错误，但最后一列似乎 合理地 常量（而且，碰巧是 √2 的近似值，通常会随着 n 变大而改善）——因此，，正如您预测的那样，复杂度是 O(√n).

我怎样才能在这个 while 循环中获得大 O 符号？

How can i get the Big O Notations in this while loop?

c

big-o