算法導論思考題

pingmian/2025/7/25 12:12:31/文章來源:https://blog.csdn.net/qq_46221910/article/details/147364970

2-1 在歸并排序中對小數組采用插入排序
c. 假定修改后的算法的最壞情況運行時間為 $\Theta$ (nk+nlg(n/k))，要使修改后的算法與標準的歸并排序具有相同的運行時間，作為n的一個函數，借助 $\Theta$ 記號，k的最大值是什么？
假定k= $\Theta$ (lg n)， $\begin{aligned}\Theta(nk+nlg(n/k))&=\Theta(nk+n\lg n-n\lg k)\\ &=\Theta(n\lg n+n\lg n-n\lg (\lg n))\\ &=\Theta(2n\lg n-n\lg (\lg n)) \end{aligned}$
當n趨近于無窮大時，lg n的增長速度遠快于lg(lg n)，所以后者可忽略，上式寫為 $\Theta$ (nlg n)
2-2
BUBBLESORT(A)
1 for i=1 to A.len-1
2 $\quad$ for j=A.len downto i+1
3 $\qquad$

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/77511.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/77511.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/77511.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！