알고리즘의 시간 복잡도 (Big Oh 표기법)

Question

안녕하세요, 간단한 질문입니다. 알고리즘 분석을 살펴보기 시작했는데 Big-Oh 표기법을 배우려고합니다.

내가보고있는 알고리즘에는 데이터 집합을 정렬하는 데 필요한 quicksort (복잡성 O (nlog (n)))가 포함되어 있으며 그 다음 집합 자체에서 작동하는 알고리즘은 최악의 실행 시간 n/10 및 복잡도 O (n).

알고리즘의 전체적인 복잡성은 가장 높은 순서이므로 O (n) 일 것이라고 생각합니다. 따라서 퀵 정렬의 복잡성이 중복됩니다. 그러나, 누군가가 이것을 확인하거나 제가 잘못한 것을 말해 줄 수 있습니까?

Answer 1

틀린.

퀵소트는 최악의 경우 O (n^2)의 복잡도를 갖습니다. 하지만 O (nlogn) 정렬 알고리즘을 사용하더라도 O (n) 이상입니다.