數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價(jià)問題(編輯修改稿)
2024-07-18 08:45 本頁面
【文章內(nèi)容簡介】 3 4 5 6 7 8 9 10 11 Union(0,4)： 把所有的 0改為 4 4 1 2 1 4 5 6 7 8 9 10 11 Union(3,1)： 把所有的 3改為 1 4 1 2 1 4 5 10 7 8 9 10 11 Union(6,10)： 把所有的 6改為 10 4 1 2 1 4 5 10 7 9 9 10 11 Union(8,9)： 把所有的 8改為 9 4 1 2 1 4 5 10 4 9 9 10 11 Union(7,4)： 把所有的 7改為 4 4 1 2 1 4 5 9 4 9 9 9 11 Union(6,8)： 把所有的 10改為 9 4 5 2 5 4 5 9 4 9 9 9 11 Union(3,5)： 把所有的 1改為 5 4 5 11 5 4 5 9 4 9 9 9 11 Union(2,11)： 把所有的 2改為 11 4 5 4 5 4 5 9 4 9 9 9 4 Union(11,0)： 把所有的 11改為 4 數(shù)組法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(1) m Union O(n) n1 將所有元素合并到一個(gè)集合： O(m+n2) 并查集實(shí)現(xiàn)方法 2： 鏈表表示法 每個(gè)等價(jià)類用一個(gè)鏈表表示， 第一個(gè)結(jié)點(diǎn)作其代表，初始 n個(gè)鏈表 (a) 兩個(gè)集合的鏈表表示，其中一個(gè)集合c{b,c,e,h}，另一個(gè)集合 f{d,f,g}。鏈表中每個(gè)結(jié)點(diǎn)包含一個(gè)集合成員、一個(gè)指向下一個(gè)集合元素結(jié)點(diǎn)的指針以及一個(gè)指向表中第一個(gè)結(jié)點(diǎn)的指針。每一個(gè)鏈表都有頭指針和尾指針，分別指向第一個(gè)和最后一個(gè)元素結(jié)點(diǎn) (b) union(c,f)的結(jié)果，代表為 f。將第 2個(gè)鏈表拼接在第一個(gè)鏈表表尾，原第 2個(gè)鏈表的每個(gè)結(jié)點(diǎn)都需更新指向代表的指針 鏈表法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(1) m Union O(n) n1 將所有元素合并到一個(gè)集合： O(m+n2) 鏈表表示法的改進(jìn)： —— 按秩合并啟發(fā)式策略 假設(shè)每個(gè)等價(jià)類的鏈表中增加表的長度信息 在執(zhí)行 union操作時(shí)總是把較短的表拼接到較長的表上去，這可以把結(jié)點(diǎn)更新的次數(shù)限制在 O(log n)，因此 Union操作時(shí)間效率 O(logn) 改進(jìn)后的鏈表法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(1) m Union O(logn) n1 將所有元素合并到一個(gè)集合： O(m+nlogn) 并查集實(shí)現(xiàn)方法 3： 森林表示法 每一個(gè)等價(jià)類用一棵樹表示，樹中每個(gè)結(jié)點(diǎn)是集合的一個(gè)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1