java - 三重for循环的时间复杂度

Question

我以前做过什么

三个嵌套for循环的渐近分析

我正在解决这个算法的时间复杂度。看到外循环运行n次数和内循环 1 运行i次数，我应用了求和，得到两个外循环的复杂度为 n(n 加 1)/2。然后内部循环执行 j 次等于 j 从 j 为 0 到 j 为 n(n 加 1)/2 的总和。这产生了 O(n4) 的总复杂度。

问题

三个嵌套for循环的渐近分析

看来我的回答是错误的。我在哪里犯了错误？

Answer 1

你数错了。内部循环执行j次数，并且j总是小于n. 因此，对于每个 n(n-1)/2 次内循环开始，内循环的主体将执行少于 n 次，这意味着循环执行的总次数最多为 n(n -1)/2 * O(n)，最多为 O(n^3)。我认为你所做的是重复计算。您尝试使用 的“求和” ，即循环执行j的总次数。for (int j...但是该信息已经包含在您已经进行的计算中，n(n-1)/2; 再次使用该信息并将其与 n(n-1)/2 相乘是双重计算。