时间戳

首页 > 解决方案 > 带有 if-else 块的 for 循环的时间复杂度

algorithm - 带有 if-else 块的 for 循环的时间复杂度

问题描述

我想找到下面这段代码的时间复杂度。这是我的理解-

外部 for 循环将循环2n次数，在最坏的情况下i==n，我们将进入嵌套 for 循环复杂度为 的 if 块O(n^2)，计算外部 for 循环，代码块的时间复杂度将为O(n^3).

在最好的情况下 when i!=n， else 具有复杂性，O(n)而外部 for 循环是O(n)复杂性，在最好情况下为O(n^2)。

我是正确的还是我在这里遗漏了什么？

for (int i = 0; i < 2*n; i++)
{
   if (i == n)
   {
      for (int j = 0; j < i; j++)
         for (int k = 0; k < i; k++)
            O(1)
   }
   else
   {
      for (int j = 0; j < i; j++)
         O(1)
   }
}

标签： algorithmloopstime-complexitybig-o

解决方案

不。

问题“什么是 T(n)？”。你说的是“如果 i=n，那么 O(n^3)，否则 O(n^2)”。但是问题中没有 i，只有 n。

想一个类似的问题：“一周中，Pete 在星期三工作 10 小时，每隔一天工作 1 小时，Pete 一周工作的总时间是多少？”。你并没有真正回答“如果星期是星期三，那么 X，否则 Y”。您的答案必须包括周三和每隔一天的工作时间。

回到您最初的问题，星期三是 i=n 的情况，而所有其他日子都是 i!=n 的情况。我们必须把它们全部总结起来才能找到答案。

推荐阅读