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

Question

我对以下算法有些困惑。特别是，我不明白为什么第一个是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++;

Answer 1

要正式推导增长顺序，您可以按以下方式进行:

对于c' 的情况，当i = 0 时，内部循环不会执行，因此，解决方案是将赢得的外部循环“迭代”外部化'影响内循环。