3 嵌套for循环的复杂性

Question

int x = 0;
for (int i = n; i >= 3; i--) {
    for (int j = 1; j <= Math.log(i) / Math.log(2); j++) {
        for (int t = 0; t <= n; t += j) {
            x++;
        }
    }
}
System.out.println(x);

如您所见，我有 3 个 for 循环，它们的条件相互依赖。

我的分析：

第一个循环：我假设它会运行 (n-2) 次 "worst case" 场景。
第二个循环：我假设它会运行log(n)次"worst case"的场景。
第三个循环：我假设它会运行(n)次"worst case"场景。

所以我计算出3个循环的功能是： (n-2)*(log(n))*(n)=(n^2)*log(n)-(2n)*log(n) = O((n^2)*log(n))

我不确定我的计算是否正确，请多多指教！

Answer 1

处理条件相互依赖的多个嵌套循环时必须小心。简单地将它们各自的复杂性相乘可能会导致错误的结果。

内循环

这大约运行 n / j 次。精确值为floor([n + 1] / j).
中间循环

这大约运行 log2(i) 次。 j的精确范围是[0, floor(log2(i))].
外环

这可以在不影响时间复杂度的情况下反转，即(int i = 3; i <= n; i++)

综合以上求和：

数学笔记：

向下舍入的数字仅与原始值相差减 1，即：
1 / j求和为Harmonic Series，其渐近表达式为：
Stirling's approximation: log(n) + log(n-1) + log(n-2) + log(n-3) + ... = O(n log n)

应用以上内容：

因此：

内积表达式的渐近复杂度是多少-

log(3) * log(4) * log(5) * ... * log(n) ?

上限由 log(n) 项数的次方给出，即 log(n)^(n-2):

这与直接乘以最坏情况复杂度得到的结果不同O(n^2 log n)。

3 嵌套for循环的复杂性

3 nested for loops complexity

algorithm

complexity-theory

big-o

time-complexity