빅오 표기법, Python 시간 복잡도

1. Big-O Notation 빅오 표기법

가장 빠르게 증가하는 항만 고려하면 된다.(상한)

-> 연산 횟수가 3N^3 + 5N^2 + 1000000이라면 O(N^3)으로 표현

 

- 좋은 것 부터(빠른)

O(1) 상수 시간

O(logN) 로그 시간

O(N) 선형 시간

O(NlogN) 로그 선형 시간

O(N^2) 이차 시간

O(N^3) 삼차 시간

O(2^n) 지수 시간

O(N!) 팩토리얼 시간

- 나쁜 것 까지(느린)

---

예시 1) N개 데이터 합을 구하는 코드

array = [3,5,1,2,4]
sum = 0

for x in array:
	sum += x
    
print(sum)

정답: O(N)

---

예시 2) 2중 반복문을 이용한 코드

array = [3,5,1,2,4]

for i in array:
	for j in array:
    	tmp = i*j;
        print(tmp)

정답: O(N^2)

+ 모든 2중 반복문이 그런 것은 아님. 코드 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도도 고려해야 함.

---

2.  Time Complexity 시간 복잡도

빅오 표기법에 따른 시간 복잡도에 대해 알아본다.

코딩 테스트에서의 시간 제한은 보편적으로  1~5초 정도이다. (표기 없을 경우 대략 5초로 생각)

연산 횟수가 5억(500,000,000)을 넘을 때 소요 시간

C: 1~3초

Python: 5~15초(경우에 따라 PyPy가 더 빠르기도 함)

따라서 파이썬의 경우를 평균 10초로 본다면 

10초에 5억번(500,000,000) - > 1초에 5천만(50,000,000)번

(컴퓨터 성능에 따라 천차만별이지만, 채점 서버에서는 1초에 2천만(20,000,000)번 정도로 생각하자)

---

예시) O(N^3)의 알고리즘에서 N이 5000이 넘는다면 시간이 얼마나 걸릴까?

125,000,000,000번의 연산이 필요.

125,000,000,000 / 50,000,000(1초) = 2500

즉, 약 2500초 정도가 걸린다고 볼 수 있다.

 

이를 통해 생각할 수 있는 시간 제한 기준

시간제한 1초 (Python기준)
N의 범위가 500	O(N^3)인 알고리즘을 설계하면 풀 수 있다.
N의 범위가 2,000	O(N^2)인 알고리즘을 설계하면 풀 수 있다.
N의 범위가 100,000	O(NlogN)인 알고리즘을 설계하면 풀 수 있다.
N의 범위가 10,000,000	O(N)인 알고리즘을 설계하면 풀 수 있다.

 

---

파이썬 시간 측정 방법

import time
start_time = time.time() #측정 시작

#본인의 소스코드
#~~~~~~~~~~~~~~
#본인의 소스코드

end_time = time.time()
print("time:", end_time - start_time) #수행 시간 출력

---

출처

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC