分治習題課(已修改)
2025-05-22 15:46 本頁面
【正文】 習題課 四川師范大學計算機科學學院 劉芳 2 習題 2－ 8 ? 不動點問題的 O(logn)時間算法。 ? 設有 n個不同的整數排好序后存于 T[1..i]中，如存在一個下標 I，使得 T[i]=i，設計一個有效算法找到這個下標。要求算法在最壞情況下的計算時間為O(logn)。 ? 分析 四川師范大學計算機科學學院 劉芳 3 習題 2－ 9 ? 主元素問題的線性時間算法 ? 分析： ? 如存在主元 x，則 x為 T的中位數； ? 否則，如果 T的中位數不是主元，則 T無主元。 ? 因此，可以設計一個線性時間選擇算法，尋找中位數，從而判斷是否有主元。 四川師范大學計算機科學學院 劉芳 4 習題 2－ 31 ? 構造 Gray碼的分治算法 ? 分析： ? n=1 0 1 ? n=2 00 01 ? 11 10 ? n=3 000 001 011 010 ? 110 111 101 100 ? n=4 0000 0001 0011 0010 0110 0111 0101 0100 ? 1
教學課件相關推薦
鄂ICP備17016276號-1