时间复杂度取决于什么

我的博客分享了一篇关于算法复杂度的文章，链接为：[blog.gcc./post/2024/algorithmcomplexity/](blog.gcc./post/2024/algorithmcomplexity)。下面是其中的一些重要内容。

关于快速排序，它的空间复杂度中的logn是递归过程所需的内存占用。快速排序的稳定性以及是否在原地进行取决于分区函数。通常情况下，它是原地排序，但不稳定。堆排序方面，建立堆的过程需要n的时间复杂度。Tree Sort在构建时的时间复杂度为nlogn，但遍历只需要n。如果树变得极度不平衡，它的时间性能可能退化，接近于线性时间，即n^2。

关于某些数据结构操作的时间复杂度，插入和删除堆顶元素的主要逻辑是堆化，这一过程的时间复杂度是logn，因为与树的高度有关。而建立堆的过程需要n的时间复杂度，而不是nlogn。对于二叉搜索树，快速查找、插入、删除操作在平衡时的时间复杂度为logn，但如果退化成链表，则时间复杂度会变为n。至于遍历操作，时间复杂度始终是n。

我们还可以利用快速排序的核心思想，在Θ(n)的时间复杂度下查找第k个元素（无论是第k小的还是第k大的）。这意味着算法效率非常高，能够在合理的时间内处理大量数据。