我需要帮助来解决这个问题。我有正确的想法，但我需要更多来确保我理解解决方案。
假设您的朋友声称他发明了一个基于超快速比较的优先级队列。他声称插入和提取是 O(sqrt(logn)) 为什么他错了？
如果我用反证法来证明。他声称插入和提取 1 个项目是 sqrt(logn)。
因此 n 项将占用 nsqrt(logn)。如果您使用队列进行排序，他声称需要上述时间。
然而，我们知道基于比较的排序的下限是 O(nlogn)，这就是为什么你的朋友一定是错的。
当我试图解释这一点时，有人告诉我，你的朋友并没有声称他正在分类。只是他在那么短的时间内插入和提取。