并行算法的設(shè)計(jì)與分析-資料下載頁(yè)
2025-01-07 10:53本頁(yè)面
【正文】 7 1 10 2 4 11 8 5 15 3 9 6 12 16 14 1 7 10 13 2 4 8 11 3 5 9 15 6 12 14 16 1 7 4 2 3 5 9 6 1 2 4 7 3 5 6 9 1 2 4 3 分組 雙調(diào)對(duì)接比較 取 MIN 雙調(diào)對(duì)接比較 取 MIN 分組 Batcher奇偶排序 分組 Batcher奇偶排序 Parallel Algorithms 22 / Ch3 2022/2/4 Copyright USTC 分組選擇網(wǎng)絡(luò) 3. 正確性定理 P89定理 4. 復(fù)雜性分析 ? 比較器數(shù)目 ? 延遲級(jí)數(shù) Parallel Algorithms 23 / Ch3 2022/2/4 Copyright USTC 平衡分組選擇網(wǎng)絡(luò) 1. 平衡分組選擇過(guò)程 ① 將 n個(gè)輸入數(shù)據(jù)劃分成若干個(gè)大小相等的子序列； ② 使用 Batcher排序網(wǎng)絡(luò)對(duì)各子序列排序； ③ 將有序子序列形成雙調(diào)序列，進(jìn)行兩兩對(duì)接； 使用 Batcher定理形成 MAX,MIN序列，棄去 MAX序列； ④ 對(duì) MIN序列進(jìn)行雙調(diào)歸并形成有序序列； 將有序子序列形成雙調(diào)序列，進(jìn)行兩兩對(duì)接； 重復(fù)，直至恰好包含所需的 m個(gè)最小元素為止。 注 : (1)用雙調(diào)排序網(wǎng)絡(luò)取代奇偶排序網(wǎng)絡(luò) (第 1次除外 ) (2)減少了比較器的級(jí)數(shù) Parallel Algorithms 24 / Ch3 2022/2/4 Copyright USTC 平衡分組選擇網(wǎng)絡(luò) 2. 例： B(4) 奇偶排序 13 7 1 10 2 4 11 8 5 15 3 9 6 12 16 14 1 7 10 13 2 4 8 11 3 5 9 15 6 12 14 16 1 7 4 2 3 5 9 6 1 2 4 7 3 5 6 9 1 2 4 3 分組 分組 Batcher奇偶排序 雙調(diào)對(duì)接比較 取 MIN 分組 Batcher雙調(diào)排序 雙調(diào)對(duì)接比較 取 MIN B(4) 雙調(diào)排序 Parallel Algorithms 25 / Ch3 2022/2/4 Copyright USTC 平衡分組選擇網(wǎng)絡(luò) 4. 復(fù)雜性分析 ? 比較器數(shù)目 ? 延遲級(jí)數(shù) 注：平衡分組選擇網(wǎng)絡(luò)比分組選擇網(wǎng)絡(luò)快了 O(logm) Parallel Algorithms 26 / Ch3 Copyright USTC 2022/2/4 End of Chapter 3
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1