由2^x=n 得到x=logn
log8=3
题目：在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行几次比较？
选择问题的复杂度下界，已经有证明，可参考算法导论或屈婉...
由2^x=n 得到x=logn
log8=3
题目：在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行几次比较？
选择问题的复杂度下界，已经有证明，可参考算法导论或屈婉玲的算法设计与分析技术这本书。
对于选择问题，找最大问题的下界是：n-1
找第二大问题的下界是：n logn-2
答案：8 3-2=9次
-
发表于 2021-10-10 00:09
- 阅读 ( 585 )
- 分类：互联网
