英文:
Why does the worst-case cost of Quick sort in Algorithms 4th edition not match my calculated cost?
问题
I'm reading the Algorithms 4th edition, and it tells me that Quick sort uses ~N^2/2 compares in the worst case since N+(N-1)+(N-2)+...+2+1=(N+1)N/2. However, the book also tells me that the cost of partitioning is always N+1. So I'm wondering why the cost of the worst case is not (N+1)+(N-1+1)+(N-2+1)+...+(2+1)+0 = (N+1)+N+...+3=(N+4)(N-1)/2?
英文:
I'm reading the Algorithms 4th edition, and it tells me that Quick sort uses ~N^2/2 compares in the worst case since N+(N-1)+(N-2)+...+2+1=(N+1)N/2. However, the book also tells me that the cost of partitioning is always N+1. So I'm wondering why the cost of worst case is not (N+1)+(N-1+1)+(N-2+1)+...+(2+1)+0 = (N+1)+N+...+3=(N+4)(N-1)/2?
答案1
得分: 2
他们犯了一个错误？快速排序的分区需要将枢轴与每个其他元素进行比较，这恰好是 N−1 次比较。在最坏的情况下，枢轴每次都是最小值或最大值元素，因此总比较次数是 (N−1) + (N−2) + … + 1 + 0 = N(N−1)/2，即所有配对。
英文:
They goofed? Quicksort partition needs to compare the pivot to each other element, which is exactly N−1 comparisons. In the worst case, the pivot is either the min or the max element each time, so the total number of comparisons is (N−1) + (N−2) + … + 1 + 0 = N(N−1)/2, which is all pairs.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论