알고리즘 정리

알고리즘 표기법은 O() (상한)표기법,  Ω(하한)표기법 사용

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)

O(n^2) : 버블 정렬, 선택 정렬

O(nlogn): n만큼 하는거 * n을 반씩 쪼개는거: 병합 정렬

O(n) : n만큼 시간이 걸리는 거 : 선형 검색

O(logn): n을 반씩 쪼개는거: 이진 검색

O(1): 한번만 하면 되는거

선형 검색: 1~n 까지 다 찾아보는거  : O(n), Ω(1)

 

이진 검색 : n까지 반씩 검색 ( 정렬 되어 있어야 함) : O(logn), Ω(1)

 

버블 정렬: 제일 앞에서부터 뒷사람이랑 비교 후 크면 뒤로 밀려 남 O(n^2), Ω(n)

효율적일 때

- 입력 크기가 작은 경우

- 정렬이 되어있지 않을 때

비효율적일 때

- 입력 크기가 큰경우

- 이미 정렬이 되어있을 때

ex) 4 2 1 3 ---> 2 4 1 3 ---> 2 1 4 3 ---> 2 1 3 4   .... (계속 반복)

 

선택 정렬: 리스트에서 제일 작은 수 가져와 앞에 둠 O(n^2), Ω(n^2)

ex) 4 2 1 3 ---> 1 2 4 3 ---> 1 2 3 4 

 

병합 정렬  :왼쪽과 오른쪽으로 나누어 정렬 후 다시 붙임  O(log n), Ω(n log n)

장점: 시간 빠름, 단점: 메모리 많이 씀

step1: 반을 나눌 수 있는 만큼 나눔

step 2: 작은 값이 먼저 오도록 정렬 함

step 3: 정렬 된 리스트를 합침

(-----반복-----)

ex) 7 4 5 2 6 3 8 1

step1 --> [7,4,5,2] [6,3,8,1]

step1  -->[7,4] [5,2] [6,3],[8,1]

step2 --> [4,7][2,5][3,6][1,8]

step2 ~3--> [2,4,5,7][1,3,6,8]

step2 ~3--> [1,2,3,4,5,6,7,8]