1. 시간 복잡도란 ?
알고리즘의 효율성을 판단하기 위한 지표로서,
프로그램 수행에 걸리는 절대적 시간이 아닌,
알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.
연산에는 산술, 대입, 비교, 이동이 있다.
시간 복잡도, 즉 성능 측정에 사용되는 표기법은 Big-O, Big-Omega(), Theta(θ) 크게 세 가지로 나뉜다.
2. 시간복잡도 성능지표
Better < < < O(n×log n) < < O(2n) < O(n!) Worse
상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수
로그가 들어간 것들이 낮서니 기억해주세요!
log(n) 로그복잡도는 반복문의 O(n) 보다 좋은 성능이며,
nlog(n) 다항복잡도는 이중반복문 O(n2) 보다 좋은 성능입니다.
알고리즘 구현시 반복문을 사용하지 말아야 하는 경우와 사용해도 되는 경우를 잘 구분합시다.
Big-O 표기법별 대표 알고리즘
- : Operation push and pop on Stack
- g n): Binary Tree
- ): for loop
- ×log n): Quick Sort, Merge Sort, Heap Sort
- 2): Double for loop, Insert Sort, Bubble Sort, Selection Sort
- n): Fibonacci Sequence
중요한것은 우리가 자주사용하는 한 차원의 루프를 도는것보다, 로그 복잡도가 더 좋은것이며,
이중 반복문보다 n * log n의 복잡도가 더 낮다는것을 기억해야 합니다.
3. 시간 복잡도 표기 종류
최악 , 최고, 평균의 값을 표기하는 3가지 이름이 있다.
이중에 가장 많이 사용하는건 당연 Big-O 표기법! (최악의 경우를 고려한다)
Big-O - 최악의 경우를 나타냄 (상한 접근)
O(n): 최악의 경우 n번까지 수행되면 프로그램을 끝낼 수 있다.
Big-Omega - 최적의 경우를 나타냄 (하한 접근)
O(n): 최소 번은 수행되어야 프로그램을 끝낼 수 있다.
Theta - 평균 (Big-O 와 Big-Omega값의 평균값)
중요한건 모두 정확한 시간이나 성능 측정의 지표가 아니라, 대략적인 차원에서의 성능적 지표로 사용된다는 것이다.
위와 같이 나눌수도 있고 아래와 같이 4개의 종류로 나누어 표기하는 방법을 사용하기도 한다.
4. 시간 복잡도를 표기하는 다른 종류
Every-case anlaysis
- 입력크기(input size)에만 종속
- 입력값과는 무관하게 결과값은 항상 일정
): Worst-case analysis
- 입력크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최대인 경우 선택
): Average-case analysis
- 입력크기와 입력값 모두에 종속
- 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
- 각 입력에 대해서 확률 할당 가능
): Best-case analysis
- 입력크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우 선택
표기법 간의 관계
| 표기법 | 의미 |
| 는 보다 크다, f>g | |
| f=Ω(g) | 는 보다 크거나 같다, f≥g |
| f=θ(g) | 는 와 대략 같다, f=g |
| f=O(g) | 는 보다 작거나 같다, f≤g |
| f=o(g) | f는 g보다 작다, f<g |
5. Big-O 계산 실습
for a in range(n):
x +=a;
for b in range(n):
x +=b;
for i in range(n):
for j in range(n):
x = i * i
시간복잡도를 계산할때는 과감이 상수를 무시합니다.
얼마만큼의 연산이 걸리는지에 대한 시간적 공간적 차원적인 의미를 가지는 지표이기 때문에,
위와 같은 프로그램은 한차원의 for문이 있다 해도,
T(n) = O(n2) 이라고 표기할 수 있습니다.
+ 힙 , 정렬 , 그래프 , 자료구조별 시간, 공간 복잡도 정리표
힙의 시간복잡도
정렬의 시간복잡도
자료구조의 시간복잡도
+
자바 컬렉션 자료구조별 시간복잡도와 특징 정리글!!
피곤해서 다 못보고 자지만 정독하면 좋을것 같아 래퍼 남겨 놓슴다.
GrepIU
www.grepiu.com
래퍼뤈스
[알고리즘] 시간복잡도(Time Complexity)
이전 포스팅에서 알고리즘에 대한 개념을 설명했다. 그 중, 시간복잡도라는 개념이 나왔는데 밑의 그림을 예로 들었는데 이해가 쉬우리라 판단된다. 보이는 것처럼, "알고리즘"이 수행되는 시간
gompangs.tistory.com
https://roytravel.tistory.com/34
시간 복잡도 정리
시간 복잡도 시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로서, 알고리즘의 절대시간이 아닌, 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 수로 표기
roytravel.tistory.com
'Algorithm > 알고리즘 정리' 카테고리의 다른 글
| [Combination]- Java코드 (DFS, BFS 방식 -성능비교) (0) | 2021.12.20 |
|---|---|
| 정렬 알고리즘 (2) - 퀵, 머지, 힙, JAVA 구현코드 (0) | 2021.07.08 |
| 정렬 알고리즘(1) - 버블, 선택, 삽입 , JAVA 구현코드 (2) | 2021.07.07 |
| [자료구조] Hash란? Java로 구현코드 (0) | 2021.06.07 |
