[이것이 코딩 테스트다 with Python]_2_알고리즘 성능 평가

220128 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=Pj3IX2VehkU&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=2 

 

 

 

 

 

 

1. 복잡도 (Complexity)

: 알고리즘의 성능을 나타내는 척도

- 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

- 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

1) 빅오 표기법

: 가장 빠르게 증가하는 항만 고려

: 차수가 가장 큰 항만 남긴다 ( 계수 무시 )

 

 

 

 

2. 시간 복잡도 계산

ex) N개의 데이터 합을 계산

# n 개의 데이터의 합을 계산
array = [1, 3, 5, 4, 2]
sum = 0

for x in array :
    sum 
    sum += x

print(sum)

=> 수행 시간은 데이터의 개수 N 에 비례

=> O(N)

 

ex) 2중 반복문

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

for i in array :
    for j in array :
        sum = i * j
        print(sum)

=> O(N^2)

=> 모든 2중 반복문이 O(N^2) 는 아님

 

 

 

 

3. 요구사항에 따라 적절한 알고리즘 설계

- N 범위 500 -> O(N^3)

- N 범위 2000-> O(N^2)

- N 범위 100,000 -> O(NlogN)

- N 범위 10,000,000 -> O(N)

 

 

 

 

 

ex) 수행 시간 측정

import time
start_time = time.time()

end_time = time.time()

print("time : ", end_time - start_time)