wordpress公司網(wǎng)站插件,ftp媒體庫wordpress,小程序制作模板網(wǎng)站,wordpress站點標(biāo)題圖片文章目錄習(xí)題一、合并k個有序序列—最小堆問題描述#xff1a;合并k個有序序列使用最小堆為什么用堆#xff1f;算法步驟步驟1#xff1a;初始化堆步驟2#xff1a;重復(fù)提取和插入步驟3#xff1a;直到所有元素處理完#x1f4ca; 算法復(fù)雜度分析習(xí)題二、O(n)時間排序n個…文章目錄習(xí)題一、合并k個有序序列—最小堆問題描述合并k個有序序列使用最小堆為什么用堆算法步驟步驟1初始化堆步驟2重復(fù)提取和插入步驟3直到所有元素處理完 算法復(fù)雜度分析習(xí)題二、O(n)時間排序n個整數(shù)—基數(shù)排序問題描述在O(n)時間內(nèi)排序? 正確思路基數(shù)排序 計數(shù)排序核心思想關(guān)鍵觀察算法步驟步驟1將每個數(shù)轉(zhuǎn)換為n進(jìn)制兩位表示步驟2使用基數(shù)排序步驟3時間復(fù)雜度分析 算法復(fù)雜度分析 拓展思考習(xí)題三、判斷是否存在兩數(shù)乘積等于k—哈希表問題描述O(n)時間判斷兩數(shù)乘積哈希表方法核心思想算法步驟步驟1構(gòu)建哈希表步驟2查找匹配步驟3返回失敗 算法復(fù)雜度分析 拓展思考習(xí)題一、合并k個有序序列—最小堆問題描述合并k個有序序列假設(shè)你有k kk個已經(jīng)排好序的序列需要將它們合并成一個有序序列。示例序列1[ 1 , 4 , 7 , 10 ] [1, 4, 7, 10][1,4,7,10]序列2[ 2 , 5 , 8 ] [2, 5, 8][2,5,8]序列3[ 3 , 6 , 9 , 11 ] [3, 6, 9, 11][3,6,9,11]目標(biāo)合并成[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 ] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11][1,2,3,4,5,6,7,8,9,10,11]使用最小堆核心思想用最小堆維護k kk個序列的當(dāng)前首元素每次取出堆頂最小值然后從對應(yīng)序列取下一個元素加入堆。堆中放入每個序列的首元素堆頂即是最小值取出對應(yīng)的下一個元素放入堆會進(jìn)行排序為什么用堆找最小值堆頂就是最小值O ( 1 ) O(1)O(1)時間插入元素插入堆并調(diào)整O ( lg ? k ) O(lg k)O(lgk)時間刪除堆頂刪除并調(diào)整O ( lg ? k ) O(lg k)O(lgk)時間總時間復(fù)雜度O ( n lg ? k ) O(n lg k)O(nlgk)?算法步驟步驟1初始化堆取出k kk個子序列的首元素構(gòu)成一個最小堆。每個堆元素需要記錄值元素的值來源來自哪個序列序列編號以及在該序列中的位置索引步驟2重復(fù)提取和插入取出堆頂元素這是當(dāng)前所有序列中的最小值加入結(jié)果序列從對應(yīng)序列取下一個元素如果該序列還有元素將下一個元素加入堆調(diào)整堆維護堆的性質(zhì)單次操作復(fù)雜度O ( lg ? k ) O(lg k)O(lgk)因為堆中最多同時有k個元素而調(diào)整堆的時間復(fù)雜度與堆的高度成正比高度為log?k所以是O(lg k)。步驟3直到所有元素處理完重復(fù)步驟2直到所有子序列都為空堆也為空總操作次數(shù)n nn次每個元素處理一次總時間復(fù)雜度n × O ( lg ? k ) O ( n lg ? k ) n imes O(lg k) O(n lg k)n×O(lgk)O(nlgk)? 算法復(fù)雜度分析分析初始化堆將k kk個元素加入堆時間復(fù)雜度O ( k lg ? k ) O(k lg k)O(klgk)主循環(huán)處理n nn個元素每次操作包括取出堆頂O ( lg ? k ) O(lg k)O(lgk)插入新元素O ( lg ? k ) O(lg k)O(lgk)總時間O ( n lg ? k ) O(n lg k)O(nlgk)總時間復(fù)雜度O ( k lg ? k ) O ( n lg ? k ) O ( n lg ? k ) O(k lg k) O(n lg k) O(n lg k)O(klgk)O(nlgk)O(nlgk)說明當(dāng)n ≥ k n geq kn≥k時通常情況O ( n lg ? k ) O(n lg k)O(nlgk)是主導(dǎo)項。記憶口訣k個序列要合并最小堆來幫忙每次取出堆頂值對應(yīng)序列補新元n次操作lgk總復(fù)雜度nlgk習(xí)題二、O(n)時間排序n個整數(shù)—基數(shù)排序問題描述在O(n)時間內(nèi)排序關(guān)鍵約束元素個數(shù)n nn值域范圍[ 0 , n 2 ? 1 ] [0, n^2-1][0,n2?1]時間復(fù)雜度要求O ( n ) O(n)O(n)為什么不能用常規(guī)排序比較排序快速排序、歸并排序等下界是O ( n lg ? n ) O(n lg n)O(nlgn)不符合要求計數(shù)排序值域是[ 0 , n 2 ? 1 ] [0, n^2-1][0,n2?1]需要O ( n 2 ) O(n^2)O(n2)空間時間復(fù)雜度O ( n n 2 ) O ( n 2 ) O(n n^2) O(n^2)O(nn2)O(n2)不符合要求? 正確思路基數(shù)排序 計數(shù)排序核心思想將每個數(shù)轉(zhuǎn)換成n nn進(jìn)制的兩位整數(shù)然后使用基數(shù)排序。關(guān)鍵觀察對于任意數(shù)a ∈ [ 0 , n 2 ? 1 ] a in [0, n^2-1]a∈[0,n2?1]可以表示為a p ? n q a p cdot n qap?nq其中p pp是高位n nn進(jìn)制下的十位0 ≤ p ≤ n ? 1 0 leq p leq n-10≤p≤n?1q qq是低位n nn進(jìn)制下的個位0 ≤ q ≤ n ? 1 0 leq q leq n-10≤q≤n?1為什么這樣表示a aa的最大值是n 2 ? 1 n^2-1n2?1p ? n q p cdot n qp?nq的最大值是( n ? 1 ) ? n ( n ? 1 ) n 2 ? n n ? 1 n 2 ? 1 (n-1) cdot n (n-1) n^2 - n n - 1 n^2 - 1(n?1)?n(n?1)n2?nn?1n2?1?算法步驟步驟1將每個數(shù)轉(zhuǎn)換為n進(jìn)制兩位表示對于每個數(shù)a aa計算p ? a / n ? p lfloor a / n floorp?a/n?高位q a m o d n q a mod nqamodn低位步驟2使用基數(shù)排序基數(shù)排序按從低位到高位的順序排序第一輪基于低位q qq的值進(jìn)行排序使用計數(shù)排序第二輪基于高位p pp的值進(jìn)行排序使用計數(shù)排序為什么先排低位再排高位基數(shù)排序的穩(wěn)定性要求相同高位時保持低位的相對順序先排低位后排高位可以保證最終結(jié)果正確步驟3時間復(fù)雜度分析計數(shù)排序時間復(fù)雜度O ( n k ) O(n k)O(nk)其中k kk是值域大小第一輪基于q qqk n k nkn時間O ( n n ) O ( n ) O(n n) O(n)O(nn)O(n)第二輪基于p ppk n k nkn時間O ( n n ) O ( n ) O(n n) O(n)O(nn)O(n)總時間O ( n ) O ( n ) O ( n ) O(n) O(n) O(n)O(n)O(n)O(n)? 算法復(fù)雜度分析分析轉(zhuǎn)換階段將每個數(shù)轉(zhuǎn)換為n進(jìn)制兩位O ( n ) O(n)O(n)第一輪計數(shù)排序基于q qq值域[ 0 , n ? 1 ] [0, n-1][0,n?1]O ( n n ) O ( n ) O(n n) O(n)O(nn)O(n)第二輪計數(shù)排序基于p pp值域[ 0 , n ? 1 ] [0, n-1][0,n?1]O ( n n ) O ( n ) O(n n) O(n)O(nn)O(n)總時間復(fù)雜度O ( n ) O ( n ) O ( n ) O ( n ) O(n) O(n) O(n) O(n)O(n)O(n)O(n)O(n)? 拓展思考為什么值域必須是[ 0 , n 2 ? 1 ] [0, n^2-1][0,n2?1]這樣才能用n nn進(jìn)制兩位表示如果值域更大需要更多位數(shù)時間復(fù)雜度會增加如果值域是[ 0 , n 3 ? 1 ] [0, n^3-1][0,n3?1]怎么辦需要3位n nn進(jìn)制數(shù)需要3輪計數(shù)排序時間復(fù)雜度仍然是O ( n ) O(n)O(n)因為每輪值域都是n nn實際應(yīng)用整數(shù)排序當(dāng)值域范圍合適時比比較排序更快字符串排序可以看作多進(jìn)制數(shù)的排序日期排序年月日可以看作多位數(shù)與其他排序?qū)Ρ缺容^排序O ( n lg ? n ) O(n lg n)O(nlgn)通用但較慢計數(shù)排序值域大時空間復(fù)雜度高基數(shù)排序值域合適時可以達(dá)到O ( n ) O(n)O(n)記憶口訣n個整數(shù)n2值域n進(jìn)制兩位來轉(zhuǎn)換基數(shù)排序兩輪走計數(shù)排序O(n)總復(fù)雜度O(n)習(xí)題三、判斷是否存在兩數(shù)乘積等于k—哈希表問題描述O(n)時間判斷兩數(shù)乘積哈希表方法核心思想對于每個元素a i a_iai?如果k kk能被a i a_iai?整除計算a j k / a i a_j k / a_iaj?k/ai?然后在數(shù)組中查找是否存在a j a_jaj?。關(guān)鍵技巧使用哈希表實現(xiàn)O ( 1 ) O(1)O(1)的查找。算法步驟步驟1構(gòu)建哈希表對于數(shù)組中的每個元素a i a_iai?如果k m o d a i 0 k mod a_i 0kmodai?0即k kk能被a i a_iai?整除計算a j k / a i a_j k / a_iaj?k/ai?將( a j , ( a i , a j ) ) (a_j, (a_i, a_j))(aj?,(ai?,aj?))存入哈希表鍵a j a_jaj?我們希望在數(shù)組中找到的值值( a i , a j ) (a_i, a_j)(ai?,aj?)一對可能的解時間復(fù)雜度遍歷n nn個元素每次操作O ( 1 ) O(1)O(1)總計O ( n ) O(n)O(n)步驟2查找匹配對于數(shù)組中的每個元素a x a_xax?檢查哈希表中是否存在鍵a x a_xax?如果存在說明找到了匹配 哈希表中存儲的是( a x , a y ) (a_x, a_y)(ax?,ay?) 這意味著存在a x × a y k a_x imes a_y kax?×ay?k返回( a x , a y ) (a_x, a_y)(ax?,ay?)時間復(fù)雜度遍歷n nn個元素每次哈希查找O ( 1 ) O(1)O(1)總計O ( n ) O(n)O(n)步驟3返回失敗如果步驟2中沒有找到任何匹配返回失敗。時間復(fù)雜度O ( 1 ) O(1)O(1) 算法復(fù)雜度分析分析步驟1遍歷n nn個元素每次檢查整除性O(shè) ( 1 ) O(1)O(1)計算除法O ( 1 ) O(1)O(1)哈希表插入平均O ( 1 ) O(1)O(1)總計O ( n ) O(n)O(n)步驟2遍歷n nn個元素每次哈希表查找平均O ( 1 ) O(1)O(1)總計O ( n ) O(n)O(n)步驟3O ( 1 ) O(1)O(1)總時間復(fù)雜度O ( n ) O ( n ) O ( 1 ) O ( n ) O(n) O(n) O(1) O(n)O(n)O(n)O(1)O(n)?注意這是平均情況下的時間復(fù)雜度。最壞情況下所有元素哈希沖突時間復(fù)雜度可能退化到O ( n 2 ) O(n^2)O(n2)但通過良好的哈希函數(shù)可以避免。 拓展思考為什么需要檢查k m o d a i 0 k mod a_i 0kmodai?0確保a j k / a i a_j k/a_iaj?k/ai?是整數(shù)數(shù)組中都是整數(shù)非整數(shù)不可能存在如果允許i j i jij怎么辦需要檢查a i 2 k a_i^2 kai2?k的情況確保數(shù)組中a i a_iai?出現(xiàn)至少2次與其他方法對比暴力枚舉O ( n 2 ) O(n^2)O(n2)慢但簡單排序雙指針O ( n lg ? n ) O(n lg n)O(nlgn)需要排序哈希表方法O ( n ) O(n)O(n)最快但需要額外空間記憶口訣兩數(shù)乘積等于k哈希表來幫忙先算a j a_jaj?存表里再查a x a_xax?在不在兩輪遍歷O(n)總復(fù)雜度O(n)