发信人: codefarmer (CodeFarmer), 信区: JobHunting
标  题: Recursion Big-O complexity little cheatsheet
发信站: BBS 未名空间站 (Sun Jan 27 14:03:28 2013, 美东)

希望对Recursion Big-O complexity 分析有些疑惑的童鞋有些帮助
Recurrence Algorithm Big-O Solution
T(n) = T(n/2) + O(1) Binary Search O(log n)        
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)   
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts)  O(n^2)     
T(n) = 2 T(n/2) + O(n)  Mergesort (average case Quicksort)  O(nlog n)


--

※ 修改:·codefarmer 於 Jan 27 14:11:30 2013 修改本文·[FROM: 108.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 108.]

发信人: caiteha (MattGor), 信区: JobHunting
标  题: Re: Recursion Big-O complexity little cheatsheet
发信站: BBS 未名空间站 (Sun Jan 27 15:56:41 2013, 美东)

good stuff        
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 67.]

发信人: codefarmer (CodeFarmer), 信区: JobHunting
标  题: Re: Recursion Big-O complexity little cheatsheet
发信站: BBS 未名空间站 (Sun Jan 27 21:42:47 2013, 美东)

希望有大牛要补充的话，能多写几个经典的
【 在 caiteha (MattGor) 的大作中提到: 】
: good stuff        



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 108.]

发信人: caiteha (MattGor), 信区: JobHunting
标  题: Re: Recursion Big-O complexity little cheatsheet
发信站: BBS 未名空间站 (Sun Jan 27 23:05:39 2013, 美东)

solution to T(n) = T(an) + T((1-a)n) + bn
where 0 < a < 1 and b>0 are constants, is O(nlogn).

还有master theorem?
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 67.]