分治習(xí)題課(已修改)
2025-05-22 15:46 本頁(yè)面
【正文】 習(xí)題課 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 2 習(xí)題 2－ 8 ? 不動(dòng)點(diǎn)問(wèn)題的 O(logn)時(shí)間算法。 ? 設(shè)有 n個(gè)不同的整數(shù)排好序后存于 T[1..i]中，如存在一個(gè)下標(biāo) I，使得 T[i]=i，設(shè)計(jì)一個(gè)有效算法找到這個(gè)下標(biāo)。要求算法在最壞情況下的計(jì)算時(shí)間為O(logn)。 ? 分析 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 3 習(xí)題 2－ 9 ? 主元素問(wèn)題的線(xiàn)性時(shí)間算法 ? 分析： ? 如存在主元 x，則 x為 T的中位數(shù)； ? 否則，如果 T的中位數(shù)不是主元，則 T無(wú)主元。 ? 因此，可以設(shè)計(jì)一個(gè)線(xiàn)性時(shí)間選擇算法，尋找中位數(shù)，從而判斷是否有主元。 四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 劉芳 4 習(xí)題 2－ 31 ? 構(gòu)造 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1