# 함수 실행 시간(running time) 계산하는 방법
우선 실행 시간 계산을 위해 단순화해야하는 것이 있다.
- 실행 시간의 개념을 흔히 우리가 라는 시간적인 개념이 아닌,
함수나 알고리즘 수행에 필요한 스텝(step) 수라고 정의해야 한다. - 이때 스텝 수는 각 코드 라인마다 고정적으로 정해져 있다(constant)고 해야한다.
# 시간 복잡도란?
시간 복잡도는 n개의 입력 데이터에 대해 알고리즘이 문제를 해결하는데에 얼만큼의 시간이 걸리는지 나타내는 것.
일반적으로 시간 복잡도를 나타내기 위해 점근적 표기법(asymptotic notation)을 사용한다.
점근적 표기법이란,
중요하지 않은 상수와 계수들을 제거해 알고리즘의 실행 시간에서 중요한 성장률에 집중하는 방법을 의미함
점근적이라는 의미는 가장 큰 영향을 주는 요소만 계산한다는 의미이다.
# 점근적 표기법
다음과 같이 세 가지가 존재한다.
- 오메가 표기법(Big-Ω notation)
- 세타 포기법(Big-θ notation)
- 빅오 표기법(Big-O notation)
# Big-O 표기법
Big-O 표기법이란 알고리즘의 효율성을 표기해주는 표기법이다.
알고리즘의 효율성을 상한선 기준으로 표시한다. 상한선을 기준으로 하여 모든 경우의 수를 포함한다.
최악의 경우로 알고리즘의 성능을 평가하여 알고리즘의 모든 경우의 수를 포괄하는 것이다.
영향력 없는 계수와 낮은 차수의 항은 무시한다.
ex) O(5N^+3N) → O(N^)
시간복잡도에서 가장 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다.
| 복잡도 | 1 | 10 | 100 |
| O(1) | 1 | 1 | 1 |
| O(log N) | 0 | 2 | 5 |
| O(N) | 1 | 10 | 100 |
| O(N log N) | 0 | 20 | 461 |
| O(N^2) | 1 | 100 | 10000 |
| O(2^N) | 1 | 1024 | 1267650600228229401496703205376 |
| O(!N) | 1 | 3628800 | 화면에 표현할 수 없음! |
- O(1) : 상수
- 알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 오직 한단계인 경우
- 즉, 입력 데이터의 개수와 관계없이 처리 시간 또는 메모리 사용량이 일정하다.
- O(N) : 선형
- 알고리즘이 문제를 해결하는 데에 필요한 단계의 수가 입력 데이터의 개수 N에 비례하는 경우
- 즉, 입력 데이터의 개수에 따라 처리 시간 또는 메모리 사용량이 선형적으로 증가
- O(N*N)
- 알고리즘이 문제를 해결하기 위해 필요한 단계의 수가 입력 데이터의 개수 N의 제곱인 경우
- O(log N) : 로그 시간
- 알고리즘이 문제를 해결하기 위해 필요한 단계의 수가 연산마다 특정 요인에 의해 감소하는 경우
- O(N log N)
- 이진 검색 : 정렬 알고리즘
- O(Cn): 지수 시간
- 알고리즘이 문제를 해결하는데에 피요한 단계의 수가 주어진 상수 값 C의 n 제곱인 경우
# 정렬 알고리즘 별 Big-O 비교
| Sorting Algorithm | 최선 | 평균 | 최악 |
| Bubble Sort(버블 정렬) | O(n2) | O(n2) | |
| Heap Sort(힙 정렬) | O(n log n) | O(n log n) | |
| Insertion Sort(삽입 정렬) | |||
| Merge Sort(합병 정렬) | O(n log n) | O(n log n) | |
| Quick Sort(퀵 정렬) | O(n log n) | ||
| Selection Sort(선택 정렬) | |||
| Shell Sort(셸 정렬) | |||
| Smooth Sort(부드러운 정렬) |
Bubble Sort(버블 정렬)
매번 연속된 두 개의 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방식(1,2번을 비교해 큰 값을 뒤로 넘김)
Heap Sort(힙 정렬)
내림 차순 정렬을 위해서 최대 힙을 구성하고 오름 차순 정렬을 위해서 최소 힙을 구성한다.
(이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조로 최대값 최소값을 쉽게 추출할 수 있는 자료구조)
Merge Sort(합병 정렬)
큰 문제를 반으로 쪼개서 해결해 나가는 분할 방식으로 배열의 크기가 1보다 작거나 같을 때까지 반복
Quick Sort(퀵 정렬)
퀵 정렬, 분할 정복을 이용하여 정렬을 수행하는 알고리즘으로 기준이 되는 값을 정하고 그 값보다 작은 값은 왼쪽 큰 값은 오른쪽으로 정렬한다. 배열의 크기가 1보다 작거나 같을 때까지 반복
Shell Sort(셸 정렬)
삽입 정렬을 보완한 알고리즘으로 삽입 정렬과 다르게 전체의 리스트를 한번에 정리하지 않고 대신 먼저 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러개의 부분 리스트를 만들고 각 부분 리스트에 삽입 정렬을 이용하여 정렬
Smooth Sort(부드러운 정렬)
힙 정렬의 변형 중 하나로 입력을 우선 순위 대기열로 구성한 다음 반복적으로 최대값을 추출한다.
# 자료 구조별 Big-O 비교
| Data Structure | ||||||
| Sorted Array | ||||||
| Array | N/A | N/A | N/A | N/A | ||
| Linked List | ) | |||||
| Doubly Linked List | ||||||
| Stack | ||||||
| Hash Table | ||||||
| Binary Search Tree | ||||||
| B-Tree | ||||||
| Red-Black Tree | ||||||
| AVL Tree |
# 시간 복잡도가 빠른 순
O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^3) > O(2^n) > O(n!)
# 시간 복잡도 예제 풀이 추천 사이트
https://dingrr.com/blog/post/알고리즘-시간복잡도-예제-15종
[알고리즘] 시간복잡도 예제 15종 | 블로그 | 딩그르르
[알고리즘] 시간복잡도 예제 15종
dingrr.com
출처
https://mirabo.tistory.com/191
[알고리즘] 시간 복잡도(Time Complexity)
알고리즘? 컴퓨터에게 내리는 지시사항을 나열한 것 시간 복잡도? 시간 복잡도는 n개의 입력 데이터에 대해 알고리즘이 문제를 해결하는데에 얼만큼의 시간(걸리는 절차 수)이 걸리는지를 나타
mirabo.tistory.com
[알고리즘] 시간복잡도 예제 15종 | 블로그 | 딩그르르
[알고리즘] 시간복잡도 예제 15종
dingrr.com
'알고리즘' 카테고리의 다른 글
| [알고리즘] 그리디(Greedy) 기법 개념 및 구현코드 (0) | 2024.03.27 |
|---|---|
| [알고리즘] 그래프 순회(DFS, BFS) (2) | 2024.03.19 |
| [알고리즘]이진 탐색 (1) | 2024.03.12 |
| [알고리즘] 순차 탐색 (1) | 2024.03.11 |
| [알고리즘] 스택 / 큐 / 환형 큐 / 연결 리스트 (0) | 2024.03.05 |
