关于树形选择排序的时间复杂度问题

Question

我看网上还有教材上说树形选择排序时间复杂度是O(n*log2n）。因为选出一个关键字要比较log2n次。但是一次选择真的只是比较了log2n次吗？ log2n只是树的深度，我认为选出1个关键字应该比较了n-1次。

Answer 1

实际上，树形选择排序的时间复杂度为O(n^2log2n)，因为每次选择都需要比较n次，而每次选择至少需要比较log2n次，所以总的时间复杂度为O(n^2log2n)。