복잡도

복잡도

• 알고리즘의 성능을 나타내는 척도
• 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미
  -> 알고리즘을 위해 필요한 연산의 횟수 계산 가능
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미
  -> 알고리즘을 위해 필요한 메모리의 양 계산 가능
  

시간 복잡도

• 알고리즘 문제를 풀 때 단순히 복잡도라고 하면 보통 시간 복잡도 의미
• Big-O 표기법 -> 빠르게 증가하는 항만을 고려 즉 함수의 상한만을 나타냄(항상 절대적이지는 않음)

코딩테스트에서

• N의 범위가 500 인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다
• N의 범위가 2000 인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다
• N의 범위가 100,000 인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다
  N의 범위가 10,000,000 인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다

공간 복잡도

• 마찬가지로 Big-O 표기법 이용

시간과 메모리 측정

수행 시간 측정 코드

import time
start_time = time.time()

#프로그램 소스코드#

end_time = time.time()
print(time: end_time - start_time)

가독성을 해치지 않는 선에서 최대한 복잡도가 낮은 프로그램을 작성해야 한다