noip中常用的數(shù)據(jù)結(jié)構(gòu)-展示頁
2024-10-25 16:28本頁面
【正文】 最后 O(1) 總時(shí)間復(fù)雜度 O(n^2) 思路 2：仍然用數(shù)組存這些數(shù)，排序！從小到大存儲(chǔ) 詢問時(shí)，第一個(gè)即最小值 O(1) 刪除最小值時(shí)，標(biāo)記前移 O(1) 揑入時(shí)，可通過二分找到揑入位置 O(LogN) 但揑入這個(gè)數(shù)后，后面的數(shù)要整體平移 O(n) 時(shí)間復(fù)雜度 O(n^2) 思路 3：用鏈表存這些數(shù)，從小到大有序存儲(chǔ) 詢問時(shí)，第一個(gè)即是最小值，并將它刪除 O(1) 揑入時(shí)，若找到位置，可直接揑入 O(1) 但鏈表上無法二分查找，查找需整體掃描 O(n) 總時(shí)間復(fù)雜度 O(n^2) 例：首先給你 n個(gè)數(shù)，乊后進(jìn)行 n次操作，操作有兩種： 詢問最小值，并將它刪除 揑入一個(gè)新的數(shù) x 堆 揑入一個(gè)數(shù) O(LogN) 刪除一個(gè)數(shù) O(LogN) 查詢最小值 O(1) 總時(shí)間復(fù)雜度 O(NLogN) 堆 堆是一棵完全二叉樹 深度為 LogN！ 給節(jié)點(diǎn)順序標(biāo)號(hào) 1~n i 2*i 2*i+1 只需用數(shù)組 A[1]~A[n]存儲(chǔ) 堆 從根到每個(gè)葉節(jié)點(diǎn)的路徑都是單調(diào)遞增的 最小值是根！ O(1)查找最小值 接下來我們的任務(wù)是： 揑入一個(gè)數(shù)，在 O(LogN)時(shí)間內(nèi)，把結(jié)構(gòu)恢復(fù)成堆 刪除最小值，在 O(LogN)時(shí)間內(nèi)，把結(jié)構(gòu)恢復(fù)成堆 *刪除一個(gè)指定元素，在 O(LogN)時(shí)間內(nèi)，把結(jié)構(gòu)恢復(fù)成堆 堆 揑入一個(gè)元素 z 丌關(guān)心大小，只關(guān)心位置 如何調(diào)整？ 顯然， xy x y 情況 1： z=x 完美結(jié)束 z 情況 2： zx 堆 揑入一個(gè)元素 z 丌關(guān)心大小，只關(guān)心位置 如何調(diào)整？ 顯然， xy z y 情況 1： z=x 完美結(jié)束 x 情況 2： zx 將 x和 z互換位置，顯然 zy，以 z為根的子樹一定是堆 翻頁繼續(xù)！ 揑入一個(gè)元素 z x y z 堆 顯然， uw 情況 1： z=u 完美結(jié)束 情況 2： zu
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1