如题,我在网上看到的这两个时间复杂度分别是O(1)和$O(log_n)$。对于快速排序(递归)的空间复杂度,在最好情况下(数组是不均匀的),那么它的空间复杂度是递归栈(树)的高度$O(log_n)$,在最坏情况下(数组是有序的),则为$O(n)$。
如果是要计算递归使用到的栈,那么堆排序不应该也去计算对应的递归栈深度吗?那么为什么是O(1)呢?
你好,堆排序的复杂度是O(nlogn)。
2.1m questions
2.1m answers
63 comments
56.6k users