0. 들어가기 앞서서
자료구조와 알고리즘을 배울때 핵심은 공간과 시간 이용이다.
공간과 시간은 거의 항상 반비례하는 경향이있다.
시간복잡도: 어떤 알고리즘이 얼마나 걸리느냐(CPU사용량)
공간복잡도: 어떤 알고리즘이 메모리를 얼마나 쓰느냐(RAM사용량)
명령이 끝날때마다 실행 횟수를 적어봅니다.
ex)
void Func(int *a, n)
{
int i=0, j=0; 1
for (i = 0 ; i < n-1 ; i++) n (i =0일때부터 i=n-1일때까지 계속 실행되죠)
for(j=i+1; j<n ; j++) (n-1) * n (가장 많이 수행되는 경우를 생각합니다.)
if (a[i] == a[j]) a[j] = 0 ; (n-1) * (n-1)
}
명령어 실행횟수를 모두 더하면 2n²-2n+2 ->상수는 생략하고 최고차항만 생각한다. => O(n²)로 표기합니다.
ex)
int Func2(int a[], int size, int key) {
int i = 0; 1
for (i = 0; i < size; i++) size + 1
if(a[i] == key) size
return i; 1
return -1; 1
}
시간복잡도 O(size)
총 실행횟수 : 2size +4 => O(N)
