시간 복잡도
프로그램의 성능을 정확히 파악할려면 어떤 것을 고려해야 할까?
1. 입력으로 들어오는 데이터의 크기
2. 프로그램이 동작하는 하드웨어의 성능
3. 프로그램을 실행/관리하는 운영체제의 성능
4. 프로그램을 빌드하는 컴파일러의 성능
5. 비동기 로직
이들을 활용해 프로그램의 성능을 확인하면 비슷한 결과는 나오겠지만 정확히 파악하는 것은 불가능하다. 그래서 컴퓨터 과학자들은 대략적인 성능을 비교하기 위해 상대적인 표기법을 사용하기로 하였다. 그것이 바로 Big-O 표기법(Big-O notation)이다. 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다.
빅오 표기법의 성능 비교는 아래와 같다.
O(1) < O(log n) < O(n) < O(n log n) < O(n제곱) < O(2n) < O(n!)(왼쪽이 가장 빠른 순서를 나타내며, 오른쪽이 가장 느린순서를 나타낸다. 왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)
시간복잡도의 종류
각 자료구조별 시간복잡도의 성능을 나타낸 표이다.
1. O(1): 입력값(N)이 증가해도 실행시간은 동일한 알고리즘, index 로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도(기본 연산 수라고 생각하면 편함)
2. O(log N): 연산이 한번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘(log 의 지수는 항상2 이다.)
3. O(N): 입력값(N)이 증가함에 따라 실행 시간도 선형적으로 증가하는 알고리즘
4. O(N log N): O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 상태
5. O(n제곱): O(N)의 알고리즘과 O(N)의 알고리즘이 중첩된 상태
6. O(2n제곱): 빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘에 해당한다.
시간 복잡도의 예제
빅오 표기법의 예제는 아래의 6가지로 나눌 수 있다.
1. O(1): 스택에서 push, pop
2. O(log n): 이진트리
3. O(n): for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n제곱): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2n제곱) : 피보나치 수열
