무작위로 빠른 정렬의 경우, 분배 비율을 25 % 이상으로 줄이는 방식으로 피벗을 선택하면 알게되었습니다. 75 %이면 실행 시간은 O(n log n)입니다. 이제 마스터 정리 (Master Theorem)에서 이것을 증명할 수 있음을 알게되었습니다.25 % -75 % 분할로 무작위로 정렬하는 빠른 정렬 피벗 선택
그러나 내 문제는 각 단계에서 25 % -75 %의 배열을 분할하면 내 T(n)을 어떻게 정의 할 것이며 어떻게 런타임 분석이 O(n log n)에 해당하는지 확인할 수 있습니까?
Master theorem을 사용하면 이러한 종류의 알고리즘의 복잡성을 찾을 수 있습니다. 이 특별한 경우에는 배열을 두 부분으로 나눌 때 각각의 부분은 초기 배열의 3/4보다 크지 않다고 가정합니다. 그런 다음 상한선을 찾으면 T(n) < 2 * T(3/4 * n) + O(n) 또는 T(n) = 2 * T(3/4 * n) + O(n)입니다. 마스터 정리는이 방정식에 대한 해답을 제공합니다.
업데이트 : 업데이트 :마스터 정리는 이러한 반복 방정식을 해결할 수 있지만이 경우 예상되는 O (n * log n)보다 나쁜 결과를 제공합니다. 그럼에도 불구하고 그것은 다른 방법으로 해결 될 수 있습니다. 피벗이 항상 작은 부분이> = 1/4 크기라는 식으로 배열을 분할한다고 가정하면 log_ {4/3} N으로 재귀 깊이를 제한 할 수 있습니다 (각 수준에서 배열의 크기가 감소하기 때문에 적어도 4/3 배 이상). 각각의 재귀 수준에서 시간 복잡성은 총 O (n)이다. 따라서 우리는 O (n) * log {4/3} n = O (n * log n) 전체적인 복잡성을 갖는다.
더욱 엄격한 분석을 원하면 Wikipedia 문서를 고려해 볼 수 있습니다. 몇 가지 좋은 증거가 있습니다.
안녕하세요 이반, 귀하의 회신에 감사드립니다. 그러나 T (n) <2 * T (3/4 * n) + O (n)에 따라 값은 a = 2, b = 4/3, d = 1입니다. 따라서 a> b^d를 의미합니다. 그래서 T (n) = O (n^log a [base b]). 그러나 T (n)은 O (nlogn)이어야합니다. 내가 어떻게 증명할 수 있는지 말해 줄래? 감사합니다 –
@SudiptaDeb 죄송합니다, 나는 마스터 정리를 조금 잊어 버렸습니다. 다음은 업데이트 된 솔루션입니다. –
설명 주셔서 감사합니다. –