Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- XML
- python
- instruction
- DoM
- Linux
- php
- DB
- control
- for
- mysql
- Class
- system
- html
- react
- Pipelining
- DS
- while
- data structure
- MacOS
- function
- DATAPATH
- javascript
- web
- github
- Algorithm
- computer
- Java
- MIPS
- architecture
- CSS
Archives
- Today
- Total
YYYEJI
[Algorithm] 시간복잡도(Time complexity)란? 본문
728x90
시간복잡도(Time complexity)란?
작성한 코드의 실행 시간을 말합니다.
작성한 코드의 반복문, 입력 값 등을 통해 대략적으로 실행 시간을 추측할 수 있습니다.
아래 그래프는
자료의 수가 증가함에 따라 소요되는 처리시간 증가율을 나타내는 그래프입니다.
하나하나 살펴보도록 하겠습니다!
O(1)
printf("Hello world!")
O(1)은 일정한 복잡도(constant complexity)이며, 입력값이 증가하더라도 시간이 증가하지 않습니다.
o(n)
for(int i = 0; i<10; i++){
printf("%d\n". i);
}
O(n)은 선형 복잡도(linear complexity)이며, 입력값이 증가함에 따라 시간이 같은 비율로 증가합니다.
O(logn)
int i = 0, j = n;
while(j>0){
i+=j;
j/=2;
}
O(log n)은 로그 복잡도(logarithmic complextify)라고 부르며, 알고리즘을 수행할 때마다 찾아야할 대상이 절반으로 줄게됩니다.
→ O(1) 다음으로 빠른 시간 복잡도를 갖습니다.
O(n²)
for(int i = 0; i<10; i++){
for(int j = 0; j<10; j++){
printf("%d x %d = %d\m", i, j, i*j);
}
}
O(n²)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가합니다.
O(2ⁿ)
int fib(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
O(2ⁿ)는 기하급수적 복잡도(exponential complexity)라고 부르며, 가장 느린 시간 복잡도를 가지고 있습니다.
◡̈
'Algorithm' 카테고리의 다른 글
[Algorithm] Greedy로 Huffman code 풀기 (0) | 2023.04.18 |
---|---|
[Algorithm] DP로 MCM(Matrix-Chain Multiplication) 풀기 (0) | 2023.04.16 |
[Algorithm] 마스터 정리 (Master Theorem) (0) | 2023.04.16 |
[Algorithm] 재귀 트리(Recursion Tree Theorem) (0) | 2023.04.16 |
[Algorithm] 점근적 표기법(Asymptotic notation) 이해하기 (0) | 2023.04.16 |