두 번째 for 루프의 시간 복잡도는 얼마입니까?

Question

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

첫 번째 for-loop는 O (n)이지만 두 번째 것은 어떨까요?

n-1 
O(Σ) 
    i=0 

왜 -1 :

Answer 1

두 번째 루프의 복잡성은 1 + 2 + 4 ... + N-1
+ 3 또는 실제로 같다? 루프 조건에 대한 변경할 수 없기
이 < 및 <=
이 프로그램이 밖으로 시도하지 않은 :

#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.... 
} 

당신은 볼 수 주어진 코드에 대한

Answer 2

n의 마지막 값에 의해 모든 결과의 증가,

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

외부 루프는 O (n) 회 실행하고 내부 루프는 그것은 O (i) 회 실행됩니다. 내부 루프 내부의 코드가 실행되는 총 횟수는 1 + 2 + 3 + ... + n-2 = ((n-2) * (n-1))/2 = (n -3n + 2)/2이다. 따라서 전체 코드의 복잡성은 O (n)입니다.