시간복잡도 빅오 표기법

Question

알고리즘을 풀다가 문득 궁금해졌는데,시간복잡도에는 표기법이 총 세 가지 있잖아요?최선의 경우를 고려한 Ω와,평균을 고려한 θ,최악의 경우를 고려한 O.보통 알고리즘 성능을 이야기할때, 빅오 표기법을 많이 사용하는데,퀵소트를 만지작 거리다가,문득 퀵소트의 시간복잡도는 보통 O(n log n)이지만, 최악의 경우 O(n^2) 일 수도 있다는게 기억이 나더라고요.이미 빅오 표기법 자체가 최악의 상황을 가정하여 알고리즘의 성능을 평가하는 것이 아닌가요?그런데 왜 O(n^2)이라 하지 않고,'보통 O(n log n)이지만 최악의 상황에는 O(n^2)이다.' 와 같이 최악의 경우를 따로 표기하나요?

코린이듈리 · Answer

최악의 경우는 데이터가 정렬되어있고, 맨앞이나 맨뒤를 피벗으러 잡았을 경우밖에 없기 때문입니다.위에서 말한 최악의 경우를 제외한 모든 경우에선 n log n의 성능이 납니다

JethroHolic · Answer

점근 표기법이 최악의 상황을 고려한다기 보다, 점근 표기법으로 나타내었을 때 해당 차수 이하의 값을 갖는다이지, 복잡도 자체는 최악 평균 최선 3개가 있습니다.시간/공간 복잡도를 표현하기 위해 점근 표기법을 사용한 것이지, 점근 표기법 자체가 복잡도를 의미하는게 아닙니다.최선 평균 최악 중 어느건지 말 안하고 복잡도가 그냥 점근 표기식으로 나타나져있다면, 해석하는 사람이 적절하게 해석해야합니다.. (그래서 명확하게 나타내주는게 중요합니다..)quick sort 말고 다른 예시를 들면hash table에서 특정 해시 값을 가진 데이터를 가지고 오는 건 일반적으로 그냥 O(1)이라고 표현하는데, 이것도 사실은 충돌나면 최악의 경우 테이블을 다 뒤져야해서 O(테이블 사이즈) 입니다. 다만 일반적/유의미한게 평균/최선인 O(1)이여서 그냥 생략하고 O(1)이라고 합니다..https://www.geeksforgeeks.org/bubble-sort/amp/Bubble sort도 최적화된 버전은 최선은 정렬되어있는 경우 검산만 하게 되는 O(n)이 있는데, 일반적으로 O(N^2)이라 하면 다들 평균/최악으로 인식하기도 하고요..

시간복잡도 빅오 표기법

2개의 답변

기술 목록