algorithm - 第二个for循环的时间复杂度是多少？

Question

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++) { 
        //Code
    }
}

我知道第一个 for 循环是 O(n)，但是第二个呢？

Answer 1

你的第二个循环的复杂度实际上等于1+2+3+4...+n-1
或者:

  n-1
O( Σ )
  i=0

为什么 -1 ?
因为您的 for 循环条件是 <而不是 <=
用这个程序试试这个:

#include <iostream>

int main()
{
    for (int n = 0; n < 100; n++) {
        int count = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                count++;
        std::cout << "n = "<< n << " : " << count << std::endl;
    }
    while (1); // Yeah, I know....
}

您可以看到所有结果都增加了最后一个值 n