时间戳

首页 > 解决方案 > 三个嵌套循环的大 O 复杂度以及 if 语句中的最后一个循环

big-o - 三个嵌套循环的大 O 复杂度以及 if 语句中的最后一个循环

问题描述

假设我们有以下代码块：

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) 复杂度的原因是什么？

标签： big-ocomplexity-theory

解决方案

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

推荐阅读