실행시간을 재서 알고리즘의 효율을 측정한다.
문제를 풀때 시간복잡도를 분석하는 습관은 좋은 것이다.
중요한건 연산자의 숫자 혹은 연산과정의 수이다.
def sumOfN(n):
sum = 0 #1번만 실행
for i in range(1, n+1):
sum += i #n번 실행
return sum
위 함수의 시간복잡도는 T(n) = 1 + n
파라미터 n은 문제의 사이즈를 의미
문제의 사이즈가 커질수록 최고 차항의 차수가 결과에 가장 많은 영향을 미친다.
이처럼 시간복잡도에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 것을 Big-O 표시법이라고 하고 O(f(n))이라고 표현한다. (order)
문제의 사이즈보다 데이터가 무엇이냐에 따라 알고리즘 성능에 더 영향을 미치기도 한다. Big-O는 최악의 경우를 표시한다.