嵌套循环分析（每个循环边界内循环）

Question

• 在我的数据结构讲座中，我得到了关于算法和时间复杂度的作业。我实际上找不到为此需要做的事情。

Question : What is the time-complexity of this algorithm ?

• 我的解决方案是逐个循环分析，删除每个循环本身的常量和低阶项。因此，彼此之间存在三个循环。复杂度应该是O(n³)。关键是最里面的循环是动态限制的。

What is the mistake on this table ( if there is ) :

int c = 0;
for (int i = 0; i < n * n; ++i)
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < j * 2; ++k)
            c = c + 1;
return c;

欢迎大家回答。

Answer 1

为了计算时间复杂度，您可以尝试评估最内层循环的迭代次数。

• k 上的循环计算一个简单表达式 2 * j 次。
• j 上的循环运行 n 次。因此，内部循环运行 2 * n * (n + 1) / 2，这简化为 n * (n + 1).
• 外循环运行 n * n 次。因此，内部循环正好运行 n * n * n * (n + 1) 次。

对主导项进行化简，得到的时间复杂度为n⁴.

然而，一个非常精明的编译器会将这种复杂性降低到常数时间 O(1) 并生成代码：

return n * n * n * (n + 1);

在 Godbolt's compiler explorer 上尝试这个表明 none 的常见编译器目前已经实现了这一点，尽管 clang 竭尽全力试图用深不可测的 SIMD 代码优化代码。