[알고리즘] 시간복잡도란? 빅오표기법을 사용하는 이유?

1. 시간 복잡도
2. 빅오 표기법
3. 정렬 알고리즘

시간 복잡도(Time Complexity) 
시간 복잡도는 왜 필요한가? 알고리즘 中 최선의 방법을 찾기 위하여.

(학교 수업을 바탕으로 생각한 그적 피셜) 우리는 알고리즘의 효율성 즉, 실행시간은 컴퓨터가 해당 알고리즘을 실행하는 속도에 의존적이다. 시간 복잡도를 이용해 최선의 방법을 찾음으로써 알고리즘의 효율성을 따질 수 있다. 알고리즘 실행속도는 코드, 언어, 컴파일러, 컴퓨터의 스펙 등 다양한 요인에 따라서 수행 시간이 달라진다. 그럼 어떻게 알고리즘 실행 시간을 측정할 수 있을까? 매 시간 알고리즘의 정확한 실행 시간을 측정하기 어렵기 때문에 우리는 알고리즘의 환경적 요인들을 날려버린다. 알고리즘의 환경적 요인을 날려버린 상황에서 우리는 알고리즘을 근사화 혹은 단순화하여 Best-case, Worst-case, Average-case를 찾을 수 있을 것이다. 우리는 무엇을 고려해야할지 감이 잡히는가? worst-case이다. best-case를 고려하는 것은 알고리즘이 항상 최선의 값이 나오지 않기 때문에 의미 없는 케이스에 해당되며, 따라서 worst-case에 대한 시간복잡도가 의미가 있다고 말할 수 있다. 빅-O는 알고리즘의 상한선을 표현하기 때문에 앞서 말했던 worst-case를 고려해야하는 우리는 알고리즘의 효율성을 빅-O로 표현할 수 있다. 추가적으로 빅-O는 input(n)에 대한 추상적인 증가 연산이 이뤄지기 때문에 상수가 중요하지 않다.

1. 환경에 따라 수행 시간이 달라짐
  (ex. 코드, 언어, 컴파일러, 컴퓨터 스펙, "입력으로 주어지는 데이터 크기" 등에 영향을 받음)

2. "추상화" >> 환경적 요인을 날려버림(알고리즘은 추상적 개념이다.) >> 실체화
   추상적인 알고리즘 본체에 대한 "수행 시간"의 개념이 필요함. 따라서 시간 복잡도를 사용한다.

3. n(인풋)에 대한 함수 // n에 대한 증가함수
수행되는 "기본 연산"의 개수 = CPU에서 사용되는 instruction
수행되는 기본 연산의 개수에 비례함.
(ex. n자리 정수 곱셈 : 100자리 곱셈이 2자리 곱셈보다 훨씬 더 많은 기본 연산(한 자릿수 곱셈)을 필요로 함.

그때마다 정확한 f(n)을 찾아내기 어렵기 때문에 근사화 혹은 단순화된 경우를 고려함.
- Best-case // 최선에 대한 방법 : 연산은 가장 적고 빠르게, 수행시간의 하한(의미 없는 case)
- Worst-case // 최악에 대한 방법 
- Average-case // 평균에 대한 방법

어떠한 방법을 가장 크게 고려해야할까?
-  Worst-Case Analysis 
 수행시간의 상한(upper bound)
-  Average-Case Analysis  

 

시간 복잡도 분석

selection sort 알고리즘

 

Select Sort  for(int i=0; i<n-1; i++){                                 // < - ++  연산자 3개  int indexMin = i;                                         // 초기화 세지 않음.  연산자 0개  for(int j=i+1; j<n; j++){                                 // 1개 혹은 2개  if(A[j] < A[indexMin])  indexMin = j;                // [] < [] 3개(메모리 엑세스 포함)  }                                                                 // 총 안쪽 for문의 반복 6(n-i)+1                                                                    +1은 int j=i+1에서 +1에 해당  int temp = A[indexMin];                               // [] 1개  A[indexMin] = A[i];                                      // [] = [] 3개  A[i] = temp;                                               // [] = 2개 총 6개  }                                                                 // 바깥쪽 for문을 한번 반복할 때                                                                    수행되는 횟수 : 6(n-i)+10

전체 반복은 0부터 n-2까지 이므로 총 시간 복잡도(최악의 경우)는 f(n)=3n²+13n-16
빅오 표기법으로 최대 차항에서 상수를 지우고.. O(n²)이다.

시간 복잡도와 빅오 표기법은 서로 연관된 개념이 아닌 그저 두 함수 간의 관계를 나타내기에 적절하기 때문에 빅오 표기법을 사용.
  >> "함수의 증가속도"를 비교하기에 좋음

★★
f(n) = O(g(n)) 으로 표현하는 것은 f(n) ≤ O(g(n)) 함수 f의 증가속도가 g보다 빠르지 않다.  //빅오
f(n) = Ω(g(n)) 으로 표현하는 것은 f(n) ≥ Ω(g(n)) 함수 f의 증가속도가 g보다 느리지 않다.  //빅오메가
f(n) = Θ(g(n)) 으로 표현하는 것은 f(n) = Θ(g(n)) 함수 f의 증가속도가 g랑 비슷하다.        //빅세타
★★

증가속도란? n이 무한으로 갈 때(극한으로 설정), 결국 누가 더 빨리 증가하나.

f(n) = Ω(g(n))
g(n) = O(f(n))  // 기준이 무엇이냐에 따라서 표현이 달라지지만, 서로 동일한 의미를 지님

lim n을 무한을 보낼 때, g(n) / f(n) 은
 - 빅오 : 무한으로 발산하거나 양수로 수렴
lim n을 무한을 보낼 때, f(n) / g(n) 은
 - 빅오메가 : 무한으로 발산하거나 양수로 수렴
f(n)=O(g(n))이고, f(n)=Ω(g(n)) 일 때, lim n을 무한대로 보낼 때, f(n)/g(n)은
 - 빅세타 : 0이 아닌 양수로 수렴

정확하게 해석하는 것이 아닌 "표현적으로" 보자.
f(n)=O(n²)  >> 해당 식의 의미는 f(n)이 n² 보다 작거나 같다는 의미를 지닌다.
   따라서 맞는 의미이며, "표현적"으로 보는 것이 중요하다.

상한 표현이 틀린 표현은 아니지만 의미가 없는 표현일 수 있다. >> 이런식으로 이해하기.

Q. 맞는 표현은?
f(n)=O(n^2) f(n)=O(n^3) f(n)=O(n^100)
f(n)=Ω(n) f(n)=Ω(n^2)
f(n)=Θ(n^2)
 **이때 세타는 오메가와 빅오메가 두 개 모두 만족했을 경우, 만족 가능하다.
 **진짜 모르겠으면, lim로 보내버려라.

Q. 맞는 표현은?
f(n)=O(12n^2 ...) f(n)=O(2n^100 ...)
f(n)=Ω(972n ...)   f(n)=Ω(15n^2)
f(n)=Θ(0.2n^2)    f(n)=Θ(n^2 ...)

감소하지 않는 함수 중 가장 느린 함수는 f(n) = 10 (상수 함수)// O(n)


★증가 속도에 따른 함수들의 서열★

1
       >> 1과 log n 사이에 있는 함수 log log n  //엄청 많음
log n
      >> log²n  logⁿn // 엄청 많음
      >> 루트 n        // 엄청 많음
n
n*log n
n²
n³     >> 다항함수


2ⁿ     >> 지수함수


n!
nⁿ


시간 복잡도는 왜 빅오로 표기할까?
1. 최악의 경우를 고려하기 때문
2. 알고리즘의 연산수 정확X
3. 추상적 대상이므로 상수가 중요하지 X
4. n이 클 때의 수행시간의 경향이 중요

Select Sort  for(int i=0; i<n-1; i++){  int indexMin = i;  for(int j=i+1; j<n; j++){  if(A[j] < A[indexMin])  indexMin = j;  }                                                                       // 안쪽 for문 n번 반복  int temp = A[indexMin];  A[indexMin] = A[i];  A[i] = temp;  }                                                                       // 바깥쪽 for문 n번                                                                            // 안쪽(n) * 바깥(n) = 빅오표기법 O(n₂)  ※ 추상화 시킨 selection sort의 시간 복잡도 분석

-------------------------------------------------------------------------------------

정렬 알고리즘
"재귀" 
1. 선택정렬 : n개의 수 중에서 가장 작은 수를 찾음 > 맨 앞으로 이동 > 작업 반복(n-1번)
2. 삽입정렬 : i번째 수를 꺼내서 올바른 위치에 삽입      // 빅오 O(n²)
3. 버블정렬 : 이웃한 수끼리 교환       // 빅오 O(n²)
4. ★ Merge 정렬 ★ : 재귀(Divide and conquer) >> 무한을 유한으로 // 빅오 O(n log n)
5. ★ Quick 정렬 : ★ // 빅오 최악의 경우 O(n²), 평균 O(n log n)