C++의 시간 복잡도 분석에 대한 연습 문제

시간 복잡도 모든 알고리즘의 는 알고리즘이 완료하는 데 걸리는 시간입니다. 알고리즘의 효율성을 보여주고 비교 분석을 하기 위한 중요한 메트릭입니다. 우리는 알고리즘을 더 효과적으로 만드는 알고리즘의 시간 복잡도를 줄이는 경향이 있습니다.

예시 1

다음 코드 조각의 시간 복잡도 찾기

for(i= 0 ; i < n; i++){
   cout<< i << " " ;
   i++;
}

루프의 최대값은 n이지만 for 루프에서 i가 두 번 증가하여 시간이 절반으로 줄어듭니다. 따라서 시간 복잡도는 O(n)과 동일한 O(n/2)입니다.

예시 2

다음 코드 조각의 시간 복잡도 찾기

for(i= 0 ; i < n; i++){
   for(j = 0; j<n ;j++){
      cout<< i << " ";
   }
}

내부 루프와 외부 루프는 모두 n번 실행됩니다. 따라서 i의 단일 값에 대해 j는 n번 반복하고, i의 n개 값에 대해 j는 총 n*n =n을 2번 반복합니다. 따라서 시간 복잡도는 O(n 2 )입니다.

예시 3

다음 코드 조각의 시간 복잡도 찾기

int i = n;
while(i){
   cout << i << " ";
   i = i/2;
}

이 경우 각 반복 후에 i 값은 이전 값의 절반으로 바뀝니다. 따라서 시리즈는 다음과 같습니다. 따라서 시간 복잡도는 O(log n)입니다.

예시 4

다음 코드 조각의 시간 복잡도 찾기

if(i > j ){
   j>23 ? cout<<j : cout<<i;
}

코드에는 두 개의 조건문이 있습니다. 각 조건문은 시간 복잡도 =O(1)을 가지며, 그 중 2개의 경우 상수인 O(1)과 ​​동일한 O(2)입니다. .

예시 5

다음 코드 조각의 시간 복잡도 찾기

for(i= 0; i < n; i++){
   for(j = 1; j < n; j = j*2){
      cout << i << " ";
   }
}

내부 루프는 외부 루프가 n번 실행되는 동안(log n)번 실행됩니다. 따라서 i의 단일 값에 대해 j는 (log n)번 실행되고, i의 n 값에 대해 j는 총 n*(log n) =(n log n)번 반복합니다. 따라서 시간 복잡도는 O(n log n)입니다.