[2 과목] 시간 복잡도 Big-O(빅오) 표기법

📌 관련 기출문제:

• 2024년 3회 : 정렬된 N개의 데이터를 처리하는데 O(Nlog2n)의 시간이 소요되는 정렬 알고리즘은?

O(1) - 해시 함수
상수 시간의 복잡도, 입력값 n이 주어졌을 때, 문제를 해결하는데 오직 한 단계만 거친다.

O(n) - 순차 탐색
선형 시간의 복잡도, 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계이다.

O(log2n) - 이진 탐색
로그 시간의 복잡도, 입력값 n이 주어졌을 때 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

O(Nlog2n) - 퀵/병합(합병)정렬
선형 로그 시간의 복잡도, 문제 해결을 위한 단계수는 nlog2n번의 수행시간을 갖는다.

O(n^2) - 버블/삽입/선택 정렬
제곱 시간의 복잡도, 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱근이다.

O(C^n)
지수 시간의 복잡도, 문제를 해결하기 위한 단계 수는 주어진 상수값 C의 n제곱이다.