[1장] 자료구조와 알고리즘

빅오 표기법에 대한 문제풀이 내용이다.

빅오 표기법(big-O notation)이란? 알고리즘의 효율성을 표기해주는 표기법이다.

좀더 정확하게 설명하면, 해당 소스코드를 컴파일 했을때 시간 복잡도와 공간 복잡도(메모리)의 상한치가 어느정도 되는가를 알려주는 지표이기도 하다. 아래 문제들을 풀어보자.

 

08. 다음의 빅오 표기법들을 수행 시간이 적게 걸리는 것부터 나열하라.

O(1) O(n) O(log n) O(n²) O(nlog n) O(n!) O(2ⁿ)

--> O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(2ⁿ) < O(n!)

 

09. 다음의 코드에서 정확한 대입 연산, 곱셈 연산, 덧셈 연산, 비교 연산의 개수를 계산하여 정확한 시간복잡도 함수 값을 계산해보라.

(1) test(int n) 
   { 
       int i; 
       int total = 1;            ----- 대입연산 1번 
       for(i=2; i<n; i++) {     ----- 곱셈, 대입 2n-4번 
   total *= n; 
       } 
return n; 
    } 

--> 시간복잡도 2n-3 .....O(n)

 

(2) float sum(float list[], int n) 
   { 
float tempsum; 
int i; 
tempsum = 0;                  ----- 대입연산 1번 
for(i=0; i<n; i++) {            ----- 덧셈연산 2n번 
    tempsum += list[i]; 
} 
tempsum += 100;              ----- 덧셈, 대입 2번 
tempsum += 200;              ----- 덧셈, 대입 2번 
return tempsum; 
    } 

--> 시간복잡도 2n+5 .....O(n)

 

(3) void sum(int n) 
{ 
int i, b; 
b=2; ----- 대입연산 1번 
i=1;            ----- 대입연산 1번 
while(i<=n)     ----- 비교, 곱셈, 대입 2log₂ n번  
    i = i*b;      
}  
} 

--> 시간복잡도 2log₂ n + 2 .....O(log₂ n)

 

14. 다음 프로그램의 시간 복잡도를 빅오표기법으로 나타내라. 

(1) for (i=0; i<n; ++i) ++k;           ----> O(n)

(2) for (i=1; i<n; i*=2) ++k;           ----> O(log₂ n)

(3) for (i=n-1; i !=0; i/=2)   ++k;     ----> O(log₂ n)

(4) for (i=0; i<n; ++i)                   ----> O(n) 
if (i%2 ==0) 
++k;

(5) for (i=0; i<n; ++i)                  ----> O(n²) 
for (j=0; j<n; ++j) 
++k; 

(6) for (i=0; i<n; ++i)                  ----> O(n²) 
for (j=i; j<n; ++j) 
++k; 

(7) for (i=0; i<n; ++i)                  ----> O(n²) 
for (j=0; j<n; ++j) 
for (r=0; r<10; ++r) 
++k;

 

22. 크기가 n인 배열 array에서 임의의 위치 loc에 정수 value를 삽입하는 함수. 
정수가 삽입되면 그 뒤에 있는 정수들은 한 칸씩 뒤로 밀려야 함. 현재 원소의 개수 items 
(1) 
#include <stdio.h>
int items; 
int i; 
void insert_array(int* arr, int loc, int value) 
{ 
for(i = items; i > loc; i--) 
arr[i] = arr[i-1];   

arr[loc] = value; 

} 
void main() 
{ 
int arr[20]; 
int loc, value; 

printf("원소의 갯수를 입력하세요. : "); 
scanf("%d", &items); 

printf("%d개의 숫자를 입력하세요. : ", items); 
for(i=0; i<items; i++) 
scanf("%d", &arr[i]);    

printf("삽입할 원소가 들어갈 배열의 위치와 값을 입력하세요. "); 

scanf("%d %d", &loc, &value); 
insert_array(arr, loc, value); 
printf("결과 << "); 
for(i=0; i < items+1; i++)  
printf("%d ", arr[i]);   

printf("\n"); 
}

 

(2) 위의 연산의 최악, 최선, 평균적인 경우의 시간복잡도 

----> 최선 : O(1), 평균 : O(n), 최악 : O(n)