当两个嵌套循环被重写为一个循环时，时间复杂度会改变吗？

Question

嵌套for、while、if语句的时间复杂度一样吗？假设 a 是一个长度为 n.

的数组

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

上面的 for 语句将是 O(n²)。

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

上面的循环乍一看可以认为是O(n)，但最后我认为也是O(n²)。

我说得对吗？

Answer 1

Am I right?

是的！

双循环：

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

的时间复杂度为 O(n) * O(n) = O(n²) 因为每个循环都运行到 n.

单循环：

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

的时间复杂度为 O(n * n) = O(n²)，因为循环一直运行到 i = n * n = n².

Answer 2

确实还是O(n^2)。当您查看具有 len(a)*len(a) 次迭代的循环时，这一点尤其明显。

您“扁平化”了循环，但没有改变工作量，因此这只是一种“风格”改变，对复杂性没有影响。

Answer 3

我们需要根据构造恕我直言执行的操作数来确定时间复杂度。概括地说某些循环具有特定的时间复杂度是不正确的。

嵌套 for 循环的时间复杂度通常为 O(n 平方) - 并非总是如此。一些涉及的嵌套 for 循环也可能只有 O(n) 复杂度。单个 if 语句通常为 O(1)，因为您只进行基本比较。 while 循环可以是任何内容，具体取决于您的退出条件。

虽然记住诸如此类的概括可能很有用，但我们应该始终检查执行的操作数以确定复杂性。

Answer 4

让我补充一下其他答案。

Does time complexity change when two nested loops are re-written into a single loop?

如果他们做同样的工作，复杂性不会改变。 :-) 如果确实如此，那么（至少）其中之一正在做不必要的工作。

如果走得太远，我深表歉意，但让我猜猜：你的想法是：

嵌套循环 --> 相乘，即“n * n”（或“n * m”），其中“n”是“通常”。
单循环 --> 使用“n”as-is，其中“n”是“通常”。我猜你在大多数练习中都见过“n”代表“大小”。

如果这是你的想法，它只需要一个调整：对于单循环，如果“n”是循环的长度，请注意 n = len(a ) * 长度 (a);如果将“n”的含义从一个问题更改为另一个问题，则无法进行比较（对于嵌套循环，n = len(a)）。在任何情况下，这两个代码都具有 O(len(a) * len(a)) 复杂度，这是您已经发现的。

Answer 5

是的，总的来说你是对的，但有一个小警告值得一提。

在某些情况下，例如访问磁盘或将页面交换到内存中，这可能会有所不同 - 在某些情况下会有很大的不同 - 读取是否在某种块内是顺序的，访问时会产生开销不同的。有时，这对 ≥2D 矩阵中循环的顺序非常敏感。

举个具体的例子，假设我们有128字节的数据页，我们一次只能保存一个，最新的页面被缓存，我们想做一个128x128的数组并处理每个元素，我们不关心处理的顺序，但是交换页面会导致延迟是处理元素的 60 倍，并且处理需要 1s，所以延迟是 60s == 1 分钟。明白我为什么选择 x60 了吗？如果我们谈论的是 OG 1x CD-ROM 驱动器、互联网、很多东西，甚至内存，当您遇到“缓存未命中”时，这可能是保守的，尽管它可能不是那么引人注目。

我的 C 有点生疏，不要抱怨使用幻数而不是常量，但您通常可以按照以下方式做一些事情：

  uchar *buffer;
  int x, y;

  buffer = malloc(128 * 128);
  for(x=0 ; x<128 ; x++) {
    for(y=0 ; y<128 ; y++) {
      process_thingie(buffer[x*128 + y]);
    }
  }

所以处理需要 128*128 ~= 16k 秒 ~= 4½ 小时，而且你一次访问每个页面，所以又是 128 分钟，总共 6½ 小时。

相反，您可以完全忽略 2D 方面 - 正如您的问题：

  for(i=0 ; i<128*128; i++)
    process_thingie(buffer[i]);

结果相同，16k 条记录，每页交换一次，没问题：

“是的。你是对的。”

但是。假设无论出于何种原因，您都会得到 inner/outer 循环 reversed:

  for(y=0 ; y<128 ; y++) {
    for(x=0 ; x<128 ; x++) {
      process_thingie(buffer[x*128 + y]);
    }
  }

（或者把x*128 + y改成y*128 + x，一样）

嗯，那是非常不同的。每个后续访问与前一个访问的步幅为 128 字节，因此我们有义务在 每次迭代

时换入一个新页面

处理需要 128*128 ~= 16k 秒 ~= 4.5 小时，但每次交换，也就是 16k 分钟，总共约 11½ DAYS

技术上它仍然是 O(n²)...还有另一个 n 隐藏。任一实现都将以 O(n²) 相对于自身

的比例缩放例如，

CD-ROM 游戏开发人员不得不关心文件在磁盘上的 物理位置（不完全相同，但请参阅此 discussion of related issues in Myst),

现在很少有这样的问题了，SSD 的速度非常快，优化编译器 （我认为？） 通常足够聪明，可以看到发生了什么并交换两个循环（ yeah), 但它们当然不能捕获所有内容，可能有一些充分的理由需要按此顺序访问数据，您可能需要为特定任务提供最佳性能。

这在现实生活中仍然会出现，程序员有时确实需要注意它 - 我认为这是游戏机开发人员仍然需要关注的事情之一.

Answer 6

时间复杂度表示大约。任何程序的上限时间。让我们用数学方法计算两者的时间复杂度并检查。

For循环：

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

外层for循环是运行ning O(len(a))次，内层for循环是运行ning O(len(a))次。也就是运行独立于外部 for 循环 O(len(a)) 时间。

取 n=len(a)

我们可以推导出下面的函数：

F(n) = 1*n +2*n +3*n +4*n +..........+(n-1)*n+n*n (if n starts from 1)
F(n) = n(1+2++3+4+....+(n-1)+n)
F(n) = n*(n+(n+1)/2)  (Sum of n Natural Numbers)
F(n) = n^2 + 2*n + n/2 (After Solving the Equation)
F(n) = O(n^2)

For While 循环

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

我们可以直接推导它，因为它将运行 in:

len(a)*len(a) = n*n=O(n^2)

我们可以说两者的运行时间大致相等，因此复杂度保持不变。

当两个嵌套循环被重写为一个循环时，时间复杂度会改变吗？

Does time complexity change when two nested loops are re-written into a single loop?

python

loops

time-complexity