无法弄清楚这段代码的大 O 是什么。外层循环是log(n)，但是依赖于外层循环的内层循环呢？
for (int i = 1; i < A.length; i = i * 3) {
for (int j = i; j < A.length; j++) {
// Simple computation
}
}
非常感谢任何帮助:)
最佳答案
如果A.Length == n，则内层循环每次在n-i中运行。因此，程序的总复杂度为 sum(n - i) for i = 1, 3, 9, ..., n = 3^log_3(n) .由于i的个数是log_3(n)，复杂度是T(n) = n * log_3(n) - (3^(log_3(n )+1)-1) = n * log_3(n) - 3(n-1) = O(nlog(n))
关于algorithm - 这个嵌套循环相互依赖的程序的大 O 是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54349232/