堆插入的O(1)平均大小复杂度的参数

问题描述 投票:11回答:1

[Wikipedia page for binary heaps的主张是,在最坏的情况下插入为O(log n),但平均为O(1):

所需的操作数仅取决于新元素满足堆属性所必须增加的级别数,因此,插入操作的最坏情况时间复杂度为O(log n),但平均O(1)的大小写复杂度。

linked page试图证明这一点如下:

但是,平均而言,新插入的元素在树上的行进距离不大。尤其是,假设密钥分布均匀,则它有比父密钥大一半的机会。考虑到它比其祖父母更大,它有比其祖父母更大的一半的机会; daccess-ods.un.org daccess-ods.un.org考虑到其祖父母大于其祖父母,它有一半的机会大于其曾祖父母。

当然,这毫无意义吗?在我看来,如果树是随机排序的,那么新元素比其父元素大的可能性就为50/50。但是,由于大体而言,大元素下降到了底部,所以随着堆的增长,机会大大少于50/50。

是吗?

几个月来就一直在Wikipedia上...

Wikipedia页面上关于二进制堆的声明是,在最坏的情况下插入为O(log n),但平均为O(1):所需的操作数仅取决于新操作的级别数...

algorithm insert heap time-complexity
1个回答
22
投票

关于声称平均时间堆插入为O(1)的说法有更好的参考:Hayward&McDiarmid在1991年发表的论文[Average Case Analysis of Heap Building by Repeated Insertion”。 (本文链接到Wikipedia文章的当前参考文献4中。)该文献又引用了Porter&Simon在1975年发表的论文[Random insertion into a priority queue structure],该论文处理了向堆中的单个插入,并证明了平均值情况是O(1)。

© www.soinside.com 2019 - 2024. All rights reserved.