这篇Wikipidea文章http://en.wikipedia.org/wiki/Quicksort#In-place_version建议O(logn)是就地排序的时空复杂度和http://futur3googl3r.blogspot.com/2008/08/ google-interview-questions.html这个访谈网站建议它是O(n).我认为答案是O(n),但想知道我是否正确.
nha*_*tdh 11
在这两篇文章中,他们所指的空间复杂性是额外的空间(不计算存储原始数组所需的空间).除了声明额外数组的常见情况之外,这个额外空间可能来自调用堆栈.每次递归调用都会在调用堆栈上创建一个堆栈帧,占用空间,堆栈帧的数量取决于输入大小n,因此需要对其进行计数.
让我们使用维基百科文章作为参考,因为@Jim Mischel指出博客非常不一致.
对于就地快速排序,从朴素实现中修改将平均提供O(log n) 额外空间,而不是在幼稚实现中的额外空间(在所有情况下).正如博客1正确指出的那样,额外空间的最坏情况复杂性是,当算法遇到最坏情况时(排序列表;将会有递归调用,因此调用堆栈将占用额外空间).O(n) O(n)nO(n)
1 :(感谢@rici指出)但是,如果我们假设没有维基百科文章中提到的优化的实现,那么博主才是正确的.在最坏的情况下,通过首先在较小的部分上递归并对较长的部分执行尾调用,可以改进算法以使用O(log n) 额外的空间.由于较小的部分总是小于输入大小的一半,因此最多会有O(log n)递归调用.假设尾部调用优化完成,较长的部分将重用当前的堆栈帧而不会产生额外的空间.如果没有进行尾调用优化,我们总是可以用显式堆栈编写迭代实现.
| 归档时间： |
|
| 查看次数： |
15431 次 |
| 最近记录： |