堆排序的最优时间复杂度
想问一下大家 好多地方说堆排序的时间复杂度与初始序列无关 ，都是nlgn，但是个人觉得如果所有元素都相同的情况下时间复杂度是O(n)（不需要递归调整堆），这是不是代表堆排序的最佳时间复杂度是O(n)呢？是不是说堆排序最优是nlgn的说法错了呢？#C/C++#
2018-07-03 14:30 已编辑 清华大学 C++
关注
全部评论
BewareMyPower
中国科学院大学 Java
你说得对，但是这种情况太特殊了。wiki上写的堆排序best case时间复杂度是O(nlogn)，但是也补充了一句元素全都相等时是O(n)
_dom
上海交通大学 C++
这么说的话插入排序最优也是O（n）喽
相关推荐
小鹏汽车一面43人在聊
投递米哈游等公司8个岗位