三个嵌套循环的大 O 复杂性，最后一个循环在 if 语句中

Question

假设我们有以下代码块：

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

在我正在阅读的书中，复杂性是 O(n^2)，准确地说是 thetha (n^2)，但我不确定为什么。当我自己计算时，我得到 O(n^3):

1. 外层循环复杂度为 O(n)
2. 通过遵循嵌套循环规则，在第二个循环中复杂度达到 O(n^2)
3. if 语句会为真 n 次，所以到第三个循环时，复杂度将为 O(n*n^2)
4. sum++ 语句需要常数时间，所以复杂度保持在 O(n^3)

这是我的逻辑，但它似乎有缺陷。 O(n^2) 复杂度的原因是什么？

Answer 1

第二个循环运行 n 个步骤。除一个步骤外，每个步骤只需要常数时间（评估 if 语句）。第 i 步需要 O(n) 因为执行了第三个循环。所以第二个循环总共需要2n = O(n)。所以你总共得到 O(n^2).