Big-O notation

meekukin·2020년 3월 26일
0

시간 복잡도

실행시간을 재서 알고리즘의 효율을 측정한다.
문제를 풀때 시간복잡도를 분석하는 습관은 좋은 것이다.
중요한건 연산자의 숫자 혹은 연산과정의 수이다.

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

문제의 사이즈가 커질수록 최고 차항의 차수가 결과에 가장 많은 영향을 미친다.
이처럼 시간복잡도에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 것을 Big-O 표시법이라고 하고 O(f(n))이라고 표현한다. (order)

worst case, average case, best case

문제의 사이즈보다 데이터가 무엇이냐에 따라 알고리즘 성능에 더 영향을 미치기도 한다. Big-O는 최악의 경우를 표시한다.

Big-O 표기법과 성능

profile
졸꾸 !!!

0개의 댓글