双for循环的运行时间复杂度

我对以下算法有些困惑。特别是，我不明白为什么第一个是O（n），第二个是O（n ^

2）。我唯一的直觉是，第一个算法的内部和外部循环未“链接”。其次，我可以直观地看到第二种算法是O（n ^

2），但是我们将如何找到一些常数c1，c2来证明f（n）是n ^ 2的big-0和little-0？

sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
    sum++;

sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        sum++;

这两个都是

您的代码有一个方便的机制来测量时间复杂度，这就是sum变量

去用不同的值实现它n。如果您sum划一条线，那是线性的。如果不是，那不是线性的。我认为你会发现，你的第一个算法，sum将永远是准确n^2