알고리즘 선택의 기준

알고리즘 선택의 기준은?

시간복잡도 이다.

[Base]

알고리즘의 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수입니다.
수행 시간은 1억번의 연산을 1초의 시간으로 간주하여 예측합니다.

[유형]

• 빅 오메가 Ω : best case 의 연산 횟수
• 빅 세타 θ : average case 의 연산 횟수
• 빅 오 O : worst case 의 연산 횟수

특정범위의 숫자를 하나의 for문으로 찾을 경우,
빅 오메가의 시간 복잡도는 1번
빅 세타의 시간 복잡도는 N/2번
빅 오의 시간 복잡도는 N번.

코딩 테스트에선 모든 케이스를 통과해야 합격으로 판단하므로, 최악일 때인 빅-오 표기법(O(N)) 기준으로 수행시간을 계산하는 것이 좋다.

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

[Big-O 표기법별 대표 알고리즘]

• O(1) : Operation push and pop on Stack
• O(logn) : Binary Tree
• O(n) : for loop
• O(nlogn) : Quick Sort, Merge Sort, Heap Sort
• O(n2) : Double for loop, insert Sort, Bubble Sort, Selection Sort
• O(2n) : Fibonacci Sequence

차트 참조 : https://www.bigocheatsheet.com/