점근표기법1 [APS] 002. 복잡도 복잡도 복잡도(Complexity) - 알고리즘의 성능을 나타내는 척도로, 점근 표기법 을 사용 - 수행 시간을 의미하는 시간복잡도 와 필요 공간(메모리)를 의미하는 공간복잡도 로 나눔 점근 표기법(Asymptotic notation) - 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수학적 방법 빅오메가(Ω; Big-Omega) : 최선의 경우에도 작아질 수 없는 함수의 집합(하한) 빅오(O; Big-Oh) : 최악의 경우에도 커질 수 없는 함수의 집합(상한) 빅세타(Θ; Big-Theta) : 빅오메가와 빅오를 모두 만족하는 함수의 집합 - 가장 지배적인(dominant) 영향을 주는 최고차항만을 표기하며, 계수는 표기하지 않음 - 알고리즘에서는 최악의 경우를 가정하는 빅오 표기법을 주로 사.. 2023. 4. 10. 이전 1 다음
