[자료구조] 1주차 - Analisys

Analysis

성능이란 무엇인가

좋은 자료구조 - 정답을 출력, 요구하는 자원이 최소

성능(performance) 또는 효율(efficiency) = solution/resource

성능의 세가지 측면 - 최선 / 평균 / 최악 (보장의 의미)

공간 복잡도와 시간 복잡도

점근적 분석법

시간 복잡도는 매우 큰 입력에 대해서 측정

g(n)을 이용한 f(n)의 성능 표현

• g(n)은 f(n)보다 시간이 더 걸림 : g(n) ≥ f(n)
• g(n)은 f(n)보다 성능이 나쁨 : g(n) is the worst case of f(n)
• 최악의 경우에도 f(n)은 g(n)보다 좋음 : In the worst case, f(n) is better than g(n)
• f(n)의 상한은 g(n)임 : The upper bound of f(n) is g(n)

Big-O 표기법

성질 1 : f(n) = O( n )라면, f(n) = O( n^2 )이다.

성질 2 : f(n) = O(5 n^2)이라면, f(n) = O( n^2 )이다.

성질 3 : f(n) = O(n^2+ n)이라면, f(n) = O( n^2 )이다.

f(n) = O(g(n))

• f(n)은 g(n)보다 빠르다
• g(n)은 f(n)보다 느리다 -> g(n) = Ω( f(n) )

Big-O 표기 예

• 상수시간복잡도(constant time complex) : O(1)
• 선형시간복잡도(linear time complex) : O(n)
• 다항시간복잡도(polynomial time complex) : O(n^k)
• 지수시간복잡도(exponential time complex) : O(k^n)
• 로그시간복잡도(log time complex) : O(log n)