作者ajnightmare (阿华田)
看板NTUBIME100HW
标题[演算] 给谢宗廷 bubble sort tree
时间Sat Oct 24 11:54:46 2009
bubble sort tree 的leaves会刚刚好有n!个
因为n个数字排列顺序可能会有n!种
所有node的数目也跟n!有关
而这个树的深度大略是log(n!)这麽深
log(n!) <= log(n^n)
<= n*log(n)
所以每个结果走到底要花n*log(n)的时间
这只是比较不严谨的讲法
抱歉那天下课太匆促没有讲清楚
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.180.185
1F：推 P568912:谢谢原PO 我好像自己有想通一点!!! 10/31 05:07