分治策略ppt課件-資料下載頁
2025-05-06 08:34本頁面
【正文】 8 4 5 8 6 7 8 7 OK 2022/6/3 23 二分搜索所需的空間和時(shí)間 ? 所需空間 ? 存放數(shù)組 a的地址，還有 left， right， middle，及 x的地址需要存儲，共 10字節(jié) ? 計(jì)算時(shí)間 ? 成功檢索的 最好 情況和不成功檢索的 最好 情況 ? 成功檢索的 平均 情況和不成功檢索的 平均 情況 ? 成功檢索的 最壞 情況和不成功檢索的 最壞 情況 2022/6/3 24 成功檢索最好情況和不成功檢索最好情況 ? 成功檢索共有 n種 ? 不成功檢索共有 n+1種 元素 2 5 6 7 9 23 54 82 101 a 0 1 2 3 4 5 6 7 8 3 3 3 4 4 3 3 3 4 4 比較次數(shù) 3 2 3 4 1 3 2 3 4 成功比較次數(shù) 不成功比較次數(shù) 4 6 5 0 2 8 7 1 3 2022/6/3 25 ? 由圖可見，當(dāng) x在數(shù)組 A中時(shí)，算法在圓形頂點(diǎn)結(jié)束；不在 A中時(shí)，算法在方形頂點(diǎn)結(jié)束。因?yàn)?23≤924，所以比較樹的葉頂點(diǎn)都在 4或 5級上出現(xiàn)。因而元素比較的最多次數(shù)為 4。一般地有：當(dāng) 時(shí)，一次成功的折半搜索至多做 k次比較，而一次不成功的折半搜索或者做 k1次比較，或者做 k次比較。 ? ?kkn 2,2 1??2022/6/3 26 二分搜索的時(shí)間復(fù)雜度 最壞情況下的成功檢索計(jì)算時(shí)間 Θ(logn) 最壞情況下的不成功檢索計(jì)算時(shí)間 Θ(logn) 最好情況下的成功檢索計(jì)算時(shí)間 Θ(1) 最好情況下的不成功檢索計(jì)算時(shí)間 Θ(logn) 每種不成功的檢索時(shí)間都為 Θ(logn) 2022/6/3 27 二分檢索在各種情況下的檢索時(shí)間
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1