시간 복잡도
Time Complexity (시간 복잡도) 는 알고리즘의 시간적인 성능을 비교하기 위한 표현 방법입니다.
Time complexity - Wikipedia
From Wikipedia, the free encyclopedia Estimate of time taken for running an algorithm Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N as the result of input size n for each function In computer science, t
en.wikipedia.org
시간 복잡도를 표현하기 위한 방법은 다양하지만 대표적인 수학적 표현 방법으로 Big O 표기법 이 있습니다.
컴퓨터의 성능이나 입력 데이터의 크기에 따라 달라질 수 있기 때문에, O(n) 과 같은 표현으로 데이터 크기를 n 으로 표현하고 이 때 발생하는 시간 복잡도를 표현합니다.
Big O 의 복잡도 순서
아래는 Big O 의 주요 시간 복잡도의 순서와 그래프로 표현한 내용입니다.
그래프 그리는 사이트에서 대표적인 시간 복잡도 그래프를 그려봤습니다.
X축의 의미 : X값이 증가할 수록 데이터(N)가 증가한다.
Y축의 의미 : Y값이 증가할 수록 시간복잡도 이 증가한다.
성능 : X가 증가할 때, Y가 증가하는 비율이 낮을 수록 효율적이다.
시간복잡도 알고리즘 예제
| Time Complexity 시간 복잡도 표기 |
Name 이름 |
Example algorithms 알고리즘 예제 |
성능 평가 |
| 𝑂(1) | Contant Time 상수 시간 |
정렬된 배열의 중간값 찾기 (항상 일정한 시간이 걸림) |
Excellent |
| 𝑂(log n) | Logarithmic Time 로그 시간 |
Binary Search (데이터 양이 많아져도 큰 변화없음 ) |
Good |
| 𝑂(n) | Linear Time 선형 시간 |
Sequential Search (데이터 양에 비례) |
Fair |
| 𝑂(nlog n) | Linearithmic Time 선형 로그 시간 |
Quick Sort, Merge Sort (데이터 양 * 로그 ↑) |
Bad |
| 𝑂(n^2) | Quadratic Time 2차 시간 |
Bubble Sort, Insert Sort | Horrible |
| 𝑂(n^3) | Cubic Time 3차 시간 |
N*N 행렬 2개의 곱셈 반복문 3개의 중첩계산 |
Horrible |
| 𝑂(2^n) | Exponential Time 지수시간 |
피보나치 수열 | Horrible |
| 𝑂(n!) | Factirial Time | Brute Force 방식의 외판원 문제 (모든 경우의 수를 대입, 시간 ↑) |
Horrible |
※ 시간복잡도에 대해서 살펴보다 보면 Binary Search 가 효율적인 방법임을 깨닫게 되는 것 같습니다.
※ Brute Force 는 무차별적인 공격이란 의미로 가능한 모든 경우의 수를 모두 시도하는 접근 방식입니다. 비밀번호가 걸린 잠금 장치를 풀때 모든 숫자를 대입해보는 방식으로 암호학에서는 확실한 방법이라고 알려져있지만 시간이 많이 걸릴 수 있는 방법입니다.
See Also
시간 복잡도와 관련하여 검색을 통해 나오는 내용들은 Eric Rowell's Big-O Complexity Chart 의 내용을 많이 참고하고 있는 것 같아 링크를 추가로 공유합니다. (↓더보기 링크↓)
※ Sort 나 자료 구조에 대한 Time Complexity 가 함께 정리되어 있으니 참고하시면 좋을 것 같습니다.
위키피디아 내용이 조금 방대하여 찾아보면서 관련 도서와 해외 자료들을 찾아보면서 정리하고 있습니다.
※ 여기에 있지 않은 내용은 추가로 확인되면 업데이트 하도록 하겠습니다.
감사합니다.
'IT > Programming' 카테고리의 다른 글
| [알고리즘] 세그먼트 트리 ( Segment Tree ) #1 개념 소개 (0) | 2023.05.11 |
|---|---|
| [알고리즘] 이진 검색 (Binary Search) (0) | 2023.05.10 |
| [알고리즘] 순차 검색 (Sequential Search) (0) | 2023.05.07 |
| [프로그래밍 정보] 웹 기반 프로그래밍 컴파일러 - C, C++, Java, Python (0) | 2023.05.06 |
| [알고리즘] 정올 1912 번 문제 : 미로 탐색 (0) | 2023.04.26 |