我想计算这个嵌套 for 循环的 theta 复杂度:
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// statement
我会说它是 n^3，但我认为这不正确，因为每个 for 循环都不是从 1 到 n。我做了一些测试:
n = 5 -> 10
10 -> 120
30 -> 4060
50 -> 19600
所以它必须在 n^2 和 n^3 之间。我尝试了求和公式等，但我的结果太高了。虽然是 n^2 log(n)，但这也是错误的...
最佳答案
使用 Sigma Notation 是一种有效的循序渐进的方法:
关于complexity-theory - 三个嵌套for循环的渐近分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15052528/