알고리즘 study -4-

시간복잡도

-> 똑같은 문제를 해결해도 빠르게 해결하는 것이 중요
-> 같은 입력을 제공했을 때, 어느 프로그램이 더 빠른가?
-> 항상 최악의 경우(오래 걸리는)로 생각하자

---

O(100) = O(1) / 상수는 다 같다

ex>

for(int i = 0; i< n ; i++){
	for(int j = i; i < n; j++){
    	
        ...  ;
        
    }
}

n + n-1 + ... + 2 + 1 = n(n+1)/2

O(n(n+1)/2) -->> O(n^2)

---

< 수행 시간 어림짐작 하기>

대략 1억번 연산 수행 시 1초 걸린다

O(n) -> n 1억 = 1초
O(n^2) -> n 1만 1초

n이 10만으로 주어졌을 때 O(n^2) 알고리즘 은 1초 안에는 끝나지 않을 수 있다

---

< 정렬의 시간 복잡도 >

선택정렬 -> 최솟값을 찾아서 앞으로 이동시킨다
최솟값을 한 번 찾는데 O(n) 걸리며 최솟값을 n 번 찾아야 한다 --> O(n^2)

삽입정렬 -> 원소를 차례대로 정렬된 배열에 삽입
원소 하나 삽입 시 O(n) 걸리며 삽입 n 번 해야함
--> O(n^2)

버블정렬 -> 인접한 원소 비교 후 큰 수를 뒤로 보낸다
맨 뒤의 수를 정하는데 O(n) 걸리며 n개의 숫자를 최종적으로 확정해야 함 --> O(n^2)