我以前做什么
我正在解决此算法的时间复杂性。看到外部循环的运行n时间和内部循环1的运行i时间，我应用了求和运算，得出两个外部循环的复杂度为n（n加1）/ 2。然后，内部循环执行j次，等于j从j为0到j为n（n加1）/ 2的总和。这产生了O（n4）的总复杂度。
问题
似乎我的答案是错误的。我在哪里弄错了？
你算错了。内部循环执行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是重复计数。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句