앞에서 공부했는데 아직도 구하는게 좀 어렵다. 연습을 해보자...
시간 복잡도란?
알고리즘의 예상되는 수행 시간을 분석할 때 사용한다.
수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가한다.
기본 연산
- 데이터 입출력
- 산술 연산
- 제어 연산 시간 복잡도 구하기
시간 복잡도는 일반적으로 빅오 표기법으로 나타낸다.
최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타낸다.
최고차항의 성장률만 봐도 알 수 있기 때문
T(n) = n^2 + 2n + 1 -> n^2
시간 복잡도를 구할 때, 비교연산과 교환연산을 중심으로 구하면 쉽게 다가온다.
int a(int n) {
int sum = 0; //대입 연산 1회
int i = 0; //대입 연산 1회
for(i = 0; i < n; i++) //반복문 n+1회
sum += i; //덧셈 연산 n회
for(i = 0; i < n; i++) //반복문 n+1회
sum += i; //덧셈 연산 n회
return sum; //return 1회이 알고리즘의 총 연산 횟수는 4n+5,
시간 복잡도는 T(n) = 4n + 5 = O(n)
void a(int n) {
int key;
for (int i = 1;i <= n; i++){ //외부for문 n-1회
key = s[i]; //교환연산 n-1회
for (int j = i-1; j >= 0; j--){ //최대 i회
if(s[i] > key) //외부 for문 * 내부 for문
//-> 비교연산 최대 (n-1)+(n-2)...1=n(n-1)/2회
s[j+1] = s[j] // 교환연산 최대 n(n-1)/2회
else
break;
}
s[j-1] = key; // 외부for문에 의해 교환연산 n-1회
}
이 알고리즘의 총 연산 횟수는
1*(n-1) + 2*(n(n-1)/2) + 1*(n-1) = n^2+n-2 (내부 for문이 돌아갈 때) 혹은
1*(n-1) + (n-1) + 1*(n-1) = 3n-3 ,
시간복잡도는 O(n^2) 혹은 O(n)
