計(jì)算機(jī)算法導(dǎo)論_第9章(編輯修改稿)
2024-11-15 10:17 本頁面
【文章內(nèi)容簡(jiǎn)介】 /2021 Calculating expectation 18 11/12/2021 Calculating expectation 19 11/12/2021 Randomized Selection ■ Let’s show that T(n) = O(n) by substitution ? ? ? ?? ? ? ?? ? ? ???????????????12/1021,m a x1nnknknkTnnknkTnnTWhat happened here? 20 11/12/2021 What happened here? “ Split” the recurrence What happened here? What happened here? What happened here? Randomized Selection ● Assume T(n) ? for sufficiently large c: ? ?? ?? ?? ? ? ?? ? ? ?nncncnnnnnncnkkncncknnkTnnTnknknnknnk??????????????????????????????????????????????????????????????122121221121222)(2)(1211112/12/The recurrence we started with Subs itute T(n) ? for T(k) Expand arithmetic series Multiply it out 21 11/12/2021 What happened here? Subtract c/2 What happened here? What happened here? What happened here? Randomized Selection ● Assume T(n) ? for sufficiently large c: The recurrence so far Multiply it out Rearrange the arithmetic we set out to prove ? ? ? ?? ?? ?? ?en o u g h ) b i g is c if(2424241221)(ncncnccnncnT??????????????????????????????????? 22 11/12/2021 Summary of randomized orderstatistic selection ? Works fast: linear e
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1