嵌套for循环的时间复杂度很高

Question

我在这里有一个问题循环是:

for (i=0; i < n; ++i)
   for (j = 3; j < n; ++j)
           {
            ...
           }

我有点理解如何计算大哦但我不完全确定如何做到这一点.外循环执行n次,内循环对i的每个值执行i次.复杂性应该是N ^ 2(我认为).你们能详细说明这是如何计算的吗？我理解其中的一部分,但不是全部.

Answer 1

这是(n*(n-3)) = n²-3n非常大n的接近n².因此,对于Big-Oh表示法,我会写,O(n²)因为-3n可以忽略.

只是对问题中的测试进行校正:外循环执行n时间,(n-3)外循环上每次迭代的内部时间.