我这里有类似 C++ 的伪代码:
for ( i = 1; i ≤ (n – 2); i++)
for (j = i + 1; j ≤ (n – 1); j ++)
for (k = j + 1; k ≤ n; k++)
Print “Hello World”;
我相当确定这个特定代码块的时间复杂度是 O(n^3) 因为它是三层嵌套的 for 循环并且它们都至少是 n - 2 所以我概括了 (n-2) * (n-1) * n
但我一直在尝试解决实际的时间复杂度函数。这是我走到了多远,无法继续:
从 i = 1 到 n-2 的求和,从 j = (i+1) 到 n-1 的求和,从 k = (j+1) 到 n 的求和。
我理解最里面的循环执行 n - (j+1) 步,中间循环执行 (n-1)-(i+1) 步,最外层循环执行 (n-2)-i 步.我只需要一些关于如何简化求和以得出时间复杂度函数的指示。
谢谢!
最佳答案
如果有兴趣,循环遍历一次取 3 个 n 个事物的每个组合,从 (1,2,3), (1,2,4), ... 开始,到 (n-2) ,n-1,n), 即 n!/(( 3!)( (n-3)!) ) = (n)(n-1)(n-2)/6 = (n^3 - 3n^2 + 2n)/6 ,这导致 O (n^3).
关于c++ - 三重嵌套 For 循环的时间复杂度,其中索引相互依赖,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25657515/