1.검색 알고리즘
만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?
A.정렬이 되지 않은 경우, 둘은 같다고 생각한다.
최선의 경우 둘 검색 방법 모두 첫 번째 대상에서 원하는 것을 찾는다.
최악의 경우 모두 마지막 대상에서 검색이 완료되기 때문이다.
- 이진검색
이진검색은 반씩 쪼개어 정복하는 것. 가운데를 보고 내가 원하는 값(기준)에 따라 나머지 반을 나눠가며 검색한다.
정렬 되어 있을 때 유리함. - 선형검색
선형검색은 하나하나 STEP BY STEP으로 모두 탐색.
(내생각엔) 정렬이 안되어 있다면 선형을 쓰는게 나을 듯 하다.
비록 속도는 같다고 생각하지만, 더 구현하기 쉽고, 실수할 일도 적기 때문에.
2.알고리즘 표기법
실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?
A. 상한이 낮은 알고리즘이 좋다고 생각한다. 최악의 경우가 진짜 최악은 아니여야 하기 때문에. ( 속도,메모리 초과로 실패하지 않게 )
-
Big O
빅오 표기법은, ON THE ORDER의 약자로, '~만큼 정도로 커지는'이라는 의미다. 실행 시간의 상한을 나타냄.
O(n)은 n만큼 커지는 것. n이 커질 수록 선형적으로 증가.O(n^2)
O(n log n)
O(n) - 선형 검색
O(log n) - 이진 검색
O(1) -
Big Ω
빅오와 반대로, 실행 시간의 하한을 나타냄
선형검색과 이진검색 모두 실행시간의 하한은 오메가(1)이다. 운이좋다면 첫번째 케이스에 원하는 값을 찾을 수 있기 때문.Ω(n^2)
Ω(n log n)
Ω(n) - 배열 안에 존재하는 값의 개수 세기
Ω(log n)
Ω(1) - 선형 검색, 이진 검색
SO HUMAN