小编Sos*_*osy的帖子

这是一个家庭作业的问题,我不是那个找到复杂性但是我正在尽我所能!

• 三向分区是对快速排序的修改,它将元素分成小于,等于和大于枢轴的组.只需要递归地对较小和较大元素的组进行递归排序.显示如果有N个项目但只有k个唯一值(换句话说有很多重复项),则对quicksort的此修改的运行时间为O(Nk).

我的尝试:

平均情况:

树子例程将在以下索引处:

我假设具有重复项的子例程将等于(nk)

• 第一:从0到(i-1)
• 第二:我 - (i +(nk-1))
• 第三名:(i + nk) - (n-1)
• 比较次数=(nk)-1

所以,

T(n) = (n-k)-1 + Sigma from 0 until (n-k-1) [ T(i) + T (i-k)]

然后我不确定我将如何继续:S

这可能是一个非常糟糕的开始:$希望找到帮助

这是一个家庭作业问题,我被要求证明8元素二元堆需要进行8次比较.

但是当我使用一个例子时:1 2 3 4 5 6 7 8我不确定我是应该自下而上还是自上而下.但无论如何,我都试过了.

自上而下:我已经完成了8个步骤但是当我计算比较次数时,我得到13:S

在底部:我已经完成了7个步骤但是当我计算比较的数量时,我得到10:S

尝试算法后,我得到的比较:

1. H [L] = 8> H [i] = 4
2. H [L] = 8> H [i] = 2,H [r] = 5> H [最大] = 8
3. H [L] = 4> H [i] = 2
4. H [L] = 6> H [i] = 3,H [r] = 7> H [最大] = 6
5. H [L] = 8> H [i] = 1,H [r] = 7 <H [最大] = 8
6. H [L] = 4> H [i] = …