■ 시간복잡도란?
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 Big-O 표기법을 사용하여 나타내며 이 Big-O 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다.
■ 시간복잡도를 알아야 되는 이유
- 똑같은 문제를 풀더라도 빠르게 해결하는 것이 중요하다.
- 같은 입력을 제공했을 때 어느 프로그램이 더 빠른가?
- 내 프로그램의 시간복잡도는 얼마나 되는가?
■ 시간복잡도 표
| 표기 예시 | 형태 |
|---|---|
| O(1) | 상수 |
| O(log n) | 로그 |
| O(n) | 선형 |
| O(n log n) | 선형로그 |
| O(n^3) | 다차 |
| O(3^n) | 지수 |
| O(n!) | 팩토리얼 |
■ 시간복잡도 예제 1
1
2
3
4
5
a = 0
b = int(input())
c = int(input())
a = b + c
print(a)
1번 예제로 위와 같은 프로그램이 있으면 대략적으로 몇 개의 명령을 수행하는가?
간단하게 생각하면 5줄 => O(5)이다. 근데 “O(5)”와 같이 표현하지 않고 위의 시간복잡도 표처럼 6은 상수니깐 “O(1)”와 같이 표현된다.
■ 시간복잡도 예제 2
1
2
3
4
5
n = int(input())
sum = 0
for i in range(n):
sum += i
print(sum)
2번 예제로 위와 같은 프로그램이 있으면 대략적으로 몇 개의 명령을 수행하는가?
1번 예제처럼 생각하면 5줄 => O(5)이다. 그런데 for 문이 들어가 있다. for문이 n번 실행되기 때문에 이런 경우에는 O(n+5)이다. 하지만 O(n+5)에서 5는 n에 비해 시간복잡도에서 큰 영향을 주지 않는다. 따라서 시간복잡도는 O(n)이다.
■ 시간복잡도 예제 3
1
2
3
4
5
6
7
8
n = int(input())
sum = 0
for i in range(n):
for j in range(n):
sum += i * j
for i in range(n):
sum += i
print(sum)
3번 예제로 위와 같은 프로그램이 있으면 대략적으로 몇 개의 명령을 수행하는가?
위 코드를 살펴보면 2중 for문과 for문이 있다. 따라서 시간복잡도는 O(n^2 + n)이다. 하지만 위에서 설명한 것처럼 n은 n^2에 비해 큰 영향을 주지 않는다. 따라서 시간복잡도는 O(n^2)이다.
■ 수행시간을 어림짐작하기
- 대략 1억번의 연산을 수행하면 1초가 걸린다. ex) O(n) => n = 1억 => 1초
- 하지만 시간복잡도는 정확히 계산한 것이 아니기 때문에 무조건 믿어서는 안되고 많은 경험을 통해 시간을 어림짐작해야 된다.
