时间复杂度嵌套循环
Time complexity nested loop
我很难理解算法分析，尤其是下面的例子：
for (int i = 1; i < n^3; i = 2*i){
for (int j = 6*n; j > 0; j = j-2){
}
}
所以我的理解是外循环是O(nlogn)因为i乘以一个常数，我不确定n^3 有没有区别。
内循环最让我困惑。我认为它是 O(n)，因为 j 递减了一个常数，但我不确定 6*n 和 j > 0 是否有任何影响。
如果我是正确的，那么整个算法将是 O(nlogn)？虽然不确定如何表达时间复杂度T(n)。
任何见解将不胜感激。
外循环不是 O(nlogn) - 因为 i 在每个循环中乘以 2，所以它是：2, 4, 8, 16, 32... 这意味着它需要i 的 log(n^3) 步达到 n^3（对数的基数是 2）。
更正式：O(log(n^3)) = O(3logn) = O(logn)
在内部循环中，j 被初始化为 6*n 并以 2 步下降。这意味着 j 需要 6n/2 步才能达到零.
更正式：O(6n/2) = O(3n) = O(n)
所以代码部分的复杂度是O(n) * O(logn) = O(nlogn)
我很难理解算法分析，尤其是下面的例子：
for (int i = 1; i < n^3; i = 2*i){
for (int j = 6*n; j > 0; j = j-2){
}
}
所以我的理解是外循环是O(nlogn)因为i乘以一个常数，我不确定n^3 有没有区别。
内循环最让我困惑。我认为它是 O(n)，因为 j 递减了一个常数，但我不确定 6*n 和 j > 0 是否有任何影响。
如果我是正确的，那么整个算法将是 O(nlogn)？虽然不确定如何表达时间复杂度T(n)。
任何见解将不胜感激。
外循环不是 O(nlogn) - 因为 i 在每个循环中乘以 2，所以它是：2, 4, 8, 16, 32... 这意味着它需要i 的 log(n^3) 步达到 n^3（对数的基数是 2）。
更正式：O(log(n^3)) = O(3logn) = O(logn)
在内部循环中，j 被初始化为 6*n 并以 2 步下降。这意味着 j 需要 6n/2 步才能达到零.
更正式：O(6n/2) = O(3n) = O(n)
所以代码部分的复杂度是O(n) * O(logn) = O(nlogn)