시간 복잡도

Question

안녕 나는 다음과 같은 두 개의 코드 조각에 내 분석에 대한 몇 가지 의문이 분석에 대한 문의 :

1)

for (i = 1; i <= 1.5n; i++) 
     for (j = n; j >= 2; j--) 
      cout << i, j; 

외부 루프는 1.5N 시간을 실행됩니다, 그리고 내부 루프 n-2 번 실행됩니다. 따라서, 복잡도가 O (1.5N의 * (N-2) =는 O (N^2)?

2)이다

j = 1; 
    while (j < n/2) { 
     i = 1; 
     while (i < j) { 
      cout << j << i; 
      i++; 
     } 
     j++; 
    } 

루프는 N/2 회 실행되는 반면 외부와는 inner while 루프는 1 + 2 + ... + n/2 번 실행됩니다. 따라서 복잡도도 O (n^2)입니까?

제 2의 문제에 대한 분석이 확실하지 않았습니다.

도움을 주셔서 대단히 감사합니다!

Answer 1

네가 맞아. 올바른 해결책은 세는 것입니다.

참고한다 :

j = 0; 
while (j < n/2) { 
    j++; 
} 

이 갖는 복잡도 O(n) 반면 :

j = 1; 
while (j < n) { 
    j *= 2; 
} 

은 O(log n) 복잡도를 갖는다.