C++의 흥미로운 시간 복잡도 질문

시간 복잡도 알고리즘이 평균 케이스를 실행하는 데 필요한 시간으로 정의할 수 있습니다.

몇 가지 기본 함수의 시간 복잡도를 보고 계산해 보겠습니다.

방법

void counter(int n){
   for(int i = 0 ; i < n ; i++){
      for(int j = 1 ; j<n ; j += i ){
         cout<<i<<” ”<<j;
      }
      cout<<endl;
   }
}

위의 방법은 i의 모든 값에 대해 n/I번 실행됩니다. 즉, 첫 번째 반복의 경우 n회, 마지막 반복의 경우 1회입니다.

이에 따르면 총 시간 복잡도는

(n/1 + n/2 + n/3 + …. + n/n)
= n (1/1 + ½ + ⅓ + …. 1/n)

이제 (1/1 + ½ + ⅓ + ... 1/n)의 값은 O(log n)과 같습니다. .

이 코드의 시간 복잡도는 O(nlogn)입니다. .

방법

void counter(n){
   int i , j ;
   for(int i = 1 ; i <= n ; i++){
      for(j = 1; j <= log(i) ; j++){
         cout<<i<<” ”<<j;
      }
   }
}

함수의 총 복잡도는 O(log 1) + O(log 2) + O(log 3) + …입니다. + O(log n)은 O(log n!)입니다.