b*********n
发帖数: 1258 | | g*******y
发帖数: 1930 | | r****o
发帖数: 1950 | 3 what is dsw?
【在 g*******y 的大作中提到】
: 对
: dsw
| H*M
发帖数: 1268 | 4 is dsw complicated?
if we partition the array using the middle point, do it recursively, and con
nect the middle point with those two nodes returned from left child and righ
t child, the complexity will be:
T(n) = 2T(n/2) +O(1)
T(n) = O(n) too..
Am i missing something here?
【在 g*******y 的大作中提到】
: 对
: dsw
| H*M
发帖数: 1268 | 5 oh...I see
u guys mean O(1) space too?
here is the in-place O(1) and O(n) time algorithm for that.
http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf
con
righ
【在 H*M 的大作中提到】
: is dsw complicated?
: if we partition the array using the middle point, do it recursively, and con
: nect the middle point with those two nodes returned from left child and righ
: t child, the complexity will be:
: T(n) = 2T(n/2) +O(1)
: T(n) = O(n) too..
: Am i missing something here?
| h***r
发帖数: 726 | |
|
