大O嵌套循环分解循环循环

Question

我理解如何获得嵌套循环的大O的一般图片，但嵌套for循环中每个循环的操作是什么？

如果我们有：

for(int i=0; i<n; i++) 
{ 
    for(int j=i+1; j<1000; j++) 
    { 
     do something of constant time; 
    } 
} 

我们究竟是如何会得到T（N）？外循环将是n次操作，内部将是1000（n-1），内部将是c是对的？

那么T(n)=cn(1000(n-1))是吗？

Answer 1

您想折叠循环并进行双重求和。当i = 0时，您运行1000-1次。当i = 1时，运行1000 - 2次，依此类推直至n-1。这相当于从我 = 0到系列999 ñ总和 - 我，请注意，你可以单独的条款，并得到999 ñ - ñ（ñ - 1）/ 2。

这是一个很奇怪的公式，因为一旦n达到1000，内循环立即短路并且什么也不做。在这种情况下，则渐近时间复杂度实际上是O（n），因为对于高值n，代码将在常量时间内跳过内部循环。