淺談二分策略的應(yīng)用-展示頁
2025-01-29 12:56本頁面
【正文】 Camp 2023 二分策略 ?來源 一個很簡單的想法 —— 在 最壞情況下 排除 盡可能多 的干擾，以盡可能快地求得目標(biāo) ?效率 高！對信息的充分利用，盡可能去除冗余 ，減少了不必要計算 ?應(yīng)用 廣！ 5/19/2023 2 WinterCamp 2023 三種應(yīng)用類型 ?類型一：二分查找 —— 應(yīng)用于一般有序序列 ?類型二：二分枚舉 —— 應(yīng)用于退化了的有序序列 ?類型三：二分搜索 —— 應(yīng)用于無序序列 5/19/2023 3 WinterCamp 2023 類型一：二分查找 —— 應(yīng)用于一般有序序列 ?申明： “ 有序序列 ” ，僅包含兩層意思： ? 第一，它是一個 序列 ，一維的 ? 第二，該序列是 有序 的，即序列中的任意兩個元 素都是可以比較的，也就是擁有我們平時 所說的 全序關(guān)系 5/19/2023 4 WinterCamp 2023 類型一：二分查找 —— 應(yīng)用于一般有序序列 ?二分查找的一般實現(xiàn)過程： （ 1）確定查找范圍 （ 2）選擇基準(zhǔn)元素 （ 3）關(guān)鍵字比較，確定更精確的范圍 （ 4）判斷結(jié)果，如不夠精確，轉(zhuǎn)至（ 2） 5/19/2023 5 WinterCamp 2023 例一：順序統(tǒng)計問題 ? [問題描述 ] 給定一個由 n個不同的數(shù)組成的集合 S，求其中第 i小的元素。例如： S={ 3, 7, 2, 6, 8, 1, 5 }， i=4 Answer=5 5/19/2023 6 WinterCamp 2023 問題的一般解法 ? 二分查找的過程： （ 1）確定待查找元素在 S中 （ 2）在 n個元素中 隨機 取出一個記為 x，將 x作基準(zhǔn) （ 3）設(shè) S中比元素 x小的有 p個 （ 4）如果找出 x，輸出；否則轉(zhuǎn)至（ 2） ? 因為 x是 隨機選出 的，由簡單的概率分析，可得算法的復(fù)雜度期望值為 O(n)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1