d********t
发帖数: 9628 | |
b*****c
发帖数: 1103 | |
d*******u
发帖数: 186 | 3 递归实现，堆栈平均深度：O(logn).
【在 d********t 的大作中提到】
: 3X
|
c******o
发帖数: 534 | 4 递归也不用space吧？
【在 d*******u 的大作中提到】
: 递归实现，堆栈平均深度：O(logn).
|
y*******g
发帖数: 6599 | 5 你以为递归怎么实现的？
【在 c******o 的大作中提到】
: 递归也不用space吧？
|
d********t
发帖数: 9628 | 6
为啥用in-place partition还需要memory?
【在 d*******u 的大作中提到】
: 递归实现，堆栈平均深度：O(logn).
|
b*****c
发帖数: 1103 | 7 since lg(N)<100 for any N you can imagine
【在 d********t 的大作中提到】
:
: 为啥用in-place partition还需要memory?
|
d********t
发帖数: 9628 | 8
啥意思？
【在 b*****c 的大作中提到】
: since lg(N)<100 for any N you can imagine
|
q****x
发帖数: 7404 | 9 in practice you can assume any number is smaller than 2^100.
【在 d********t 的大作中提到】
:
: 啥意思？
|
d********t
发帖数: 9628 | 10
但是logN跟O（1）或者0有本质区别啊
【在 q****x 的大作中提到】
: in practice you can assume any number is smaller than 2^100.
|
|
|
b*****c
发帖数: 1103 | 11 你绝对正确，赞！
不过N受到了限制，因为排序要n*lg(N)--> N<<2^100 -> O(lg(N)) almost O(1)
【在 d********t 的大作中提到】
:
: 但是logN跟O（1）或者0有本质区别啊
|
q****x
发帖数: 7404 | 12 theory vs practice.
in theory qsort is O(N^2) in worst case. so?
【在 d********t 的大作中提到】
:
: 但是logN跟O（1）或者0有本质区别啊
|
b***e
发帖数: 383 | 13 这里说用 O(lgN)的空间并不是指交换位置或者做partition时所需要的空间，而是指在不
断递归时保存递归点（i.e., start point, end point）所需要的空间。 |
l****3
发帖数: 150 | 14 是因为递归调用要用堆栈空间
【在 d********t 的大作中提到】
:
: 但是logN跟O（1）或者0有本质区别啊
|
d********t
发帖数: 9628 | 15
正解！那在算别的任何complexity要考虑这个问题吗？
【在 l****3 的大作中提到】
: 是因为递归调用要用堆栈空间
|
c****x
发帖数: 61 | 16 要
【在 d********t 的大作中提到】
:
: 正解！那在算别的任何complexity要考虑这个问题吗？
|
d********t
发帖数: 9628 | 17
那是不是所有recursion的题目都要考虑这个？
【在 c****x 的大作中提到】
: 要
|
l****3
发帖数: 150 | 18 起码得跟面试官提一下使用递归的空间复杂度吧
不过貌似有些要求O(1) space的你用递归面试官也认可...
【在 d********t 的大作中提到】
:
: 那是不是所有recursion的题目都要考虑这个？
|
d********t
发帖数: 9628 | 19
Thanks!
【在 l****3 的大作中提到】
: 起码得跟面试官提一下使用递归的空间复杂度吧
: 不过貌似有些要求O(1) space的你用递归面试官也认可...
|
