王晓东的《计算机算法设计与分析》25页有个问题不懂。。。
书上说这个算法最坏情况下所需的计算时间T（n）满足递归式T（n）<= T(9n/10) + O(n),则由此可以推出T（n）= O（n).
为什么T（n）= O（n)？
[解决办法]
T（n）= T(9n/10) + O(n),
T(9n/10)=T(81n/100)+ O(9n/10),
T(81n/100)=T(729n/1000)+ O(81n/100),
.....
T(n)=O(n)+O(9n/10)+O(81n/100)+....=O(10n/9)=O(n)
[解决办法]
LS最后一步写错了应该是o(10n)=o(n)
