time complexity for the naive in-place sort

jackytie commented 5 years ago

in CHAPTER 12.9.1 formula 12.34 提到 "... , gets the result O(n lg n)."

我整理T(n) 的遞迴式之後得到： T(n) = 2T(n/2) + Θ( n log n ) 這樣根據master theorem會得到： T(n) = Θ( n(log n)^2 ) 跟文中敘述不符。

liuxinyu95 commented 5 years ago

多谢提出这个问题，我会尽快检查并回复。

liuxinyu95 commented 5 years ago

的确这里有误。

n个元素的计算时间为：

T(n) = T(n/2)+cn/2 +T(n/4)+c3n/4 +T(n/8)+c7n/8 +...

n/2个元素的计算时间为：

T(n/2) = T(n/4)+cn/4 +T(n/8)+c3n/8 +T(n/16)+c7n/16 +...

两式相减得：

T(n) - T(n/2) = T(n/2) + cn (1/2 + 1/2 + ...)

共log n个1/2，故计算时间的递归关系为：

T(n) = 2 T(n/2) + c n log n

利用telescope法得出结果：

T(n) = n 2T(1) + c n (log n + 1) log n /2 = \Theta(n log^2 n)

相应改动已提交到英文版https://github.com/liuxinyu95/AlgoXY/commit/55f32b513678fda5c33b5d64436f2103a187c2e0

中文版会随后修改。

liuxinyu95 commented 5 years ago

liuxinyu95 / AlgoXY