網(wǎng)站備案成功后該怎么做,百度驗(yàn)證網(wǎng)站有什么用,北京軟件設(shè)計(jì)公司,全國軟件開發(fā)培訓(xùn)班一、什么是時(shí)間復(fù)雜度和空間復(fù)雜度#xff1f;——用5段代碼講明白在算法世界里#xff0c;我們不只關(guān)心“能不能跑通”#xff0c;更關(guān)心“跑得快不快”、“占不占地方”。這就是時(shí)間復(fù)雜度和空間復(fù)雜度要解決的問題。時(shí)間復(fù)雜度#xff1a;衡量“執(zhí)行步驟”的增長趨勢(shì)不是…一、什么是時(shí)間復(fù)雜度和空間復(fù)雜度——用5段代碼講明白在算法世界里我們不只關(guān)心“能不能跑通”更關(guān)心“跑得快不快”、“占不占地方”。這就是時(shí)間復(fù)雜度和空間復(fù)雜度要解決的問題。時(shí)間復(fù)雜度衡量“執(zhí)行步驟”的增長趨勢(shì)不是看實(shí)際運(yùn)行幾毫秒而是看隨著輸入數(shù)據(jù)變大操作次數(shù)怎么變。我們用大O表示法Big O來描述這個(gè)“趨勢(shì)”。來看幾個(gè)經(jīng)典例子例1線性遍歷 →O(n)來自1.js// T(n) 3n3 function traverse(arr) { var len arr.length; // 1次 for (let i 0; i len; i) { // 循環(huán) n 次 console.log(arr[i]); // 每次循環(huán)1次 } } // T(n) 1 1 n 1 n n 3n3 → 忽略常數(shù)和低階項(xiàng) → O(n)解釋數(shù)組越長打印次數(shù)越多成正比關(guān)系。就像你數(shù)100個(gè)人的名字肯定比數(shù)10個(gè)人花10倍時(shí)間。例2雙重循環(huán) →O(n2)來自2.jsfunction traverse(arr) { var outlen arr.length; for (var i 0; i outlen; i) { var inlen arr[i].length; for (var j 0; j inlen; j) { console.log(arr[i][j]); } } } // T(n) ≈ 4n2 ... → O(n2)解釋比如一個(gè) n×n 的表格你要把每個(gè)格子都點(diǎn)一遍總共點(diǎn) n2 次。數(shù)據(jù)量翻倍操作次數(shù)變成4倍很可怕。例3指數(shù)級(jí)跳躍 →O(log n)來自3.jsfor (var i 1; i len; i i * 2) { console.log(arr[i]); } // T(n) 2logn 4 → O(log n)解釋i 每次翻倍1→2→4→8...所以循環(huán)次數(shù)是 log?(len)。比如 len1024只循環(huán)10次這是非常高效的節(jié)奏像二分查找。例4額外開數(shù)組 →O(n)空間來自4.jsfunction init(n) { var arr []; // 新開辟空間 for (var i 0; i n; i) { arr[i] i; } return arr; } // S(n) O(n)空間復(fù)雜度衡量額外內(nèi)存占用。這里新建了一個(gè)長度為 n 的數(shù)組所以空間是 O(n)。例5原地操作 →O(1)空間還是1.js// S(1) 因?yàn)橹挥幸粋€(gè)arr其他作為參數(shù)沒有額外的內(nèi)存開銷沒有 new 數(shù)組、沒遞歸、沒哈希表只是用幾個(gè)變量i, len所以空間是常數(shù)級(jí)O(1) —— 最省?總結(jié)一句話時(shí)間復(fù)雜度看“操作次數(shù)”隨輸入規(guī)模怎么漲?？臻g復(fù)雜度看“額外內(nèi)存”用了多少。我們追求時(shí)間快 空間省二、實(shí)戰(zhàn)力扣88題《合并兩個(gè)有序數(shù)組》——三指針 原地合并題目要求nums1長度為m n前m個(gè)是有用數(shù)字后n個(gè)是 0預(yù)留空間nums2長度為n把nums2合并進(jìn)nums1最終nums1變成一個(gè)有序數(shù)組不能返回新數(shù)組必須原地修改 nums1錯(cuò)誤思路從前向后合并很多人第一反應(yīng)用兩個(gè)指針從前往后比小的放前面。但問題來了nums1 后面有空位前面卻有數(shù)據(jù)如果你把小的數(shù)往前面插會(huì)覆蓋掉還沒處理的 nums1 元素比如nums1 [1,2,3,0,0,0], m3 nums2 [2,5,6], n3如果從前往后第一步把 1 放好沒問題但第二步要把 2來自 nums2放進(jìn)去時(shí)nums1[1] 原本是 2會(huì)被覆蓋而那個(gè) 2 還沒被處理所以不能從前向后正確思路從后往前 三指針利用 nums1尾部有空位的特點(diǎn)從最大的數(shù)開始填就不會(huì)覆蓋未處理的數(shù)據(jù)來看代碼一字不變function merge(nums1, m, nums2, n) { // 數(shù)組是連續(xù)的存儲(chǔ)空間所以可以從后往前合并 let i m - 1; // i 是 nums1 里面“有用數(shù)字”的最后一位的位置從0開始數(shù) let j n - 1; // j 是 nums2 里面“有用數(shù)字”的最后一位的位置 let k m n - 1; // k 是 nums1 整個(gè)數(shù)組最后一位的位置因?yàn)閚ums1已經(jīng)預(yù)留了足夠空間 // 數(shù)組是有序的 while(i 0 j 0) { // 只要 nums1 和 nums2 都還有數(shù)字沒比完就繼續(xù)比 if (nums1[i] nums2[j]) { // 如果 nums1 當(dāng)前的數(shù)字比 nums2 的大 nums1[k] nums1[i]; // 就把大的那個(gè)放到 nums1 的最后面k的位置 i--; // 然后 nums1 的指針往前面走一步看下一個(gè)數(shù)字 } else { // 否則nums2 的數(shù)字更大或一樣大 nums1[k] nums2[j]; // 把 nums2 的這個(gè)數(shù)字放到 nums1 的最后面 j--; // 然后 nums2 的指針往前面走一步 } k--; // 不管放了誰最后面的位置都要往前挪一格準(zhǔn)備放下一個(gè) } while(j 0) { // 如果 nums2 還剩下一些小數(shù)字沒放完nums1已經(jīng)放完了 nums1[k] nums2[j]; // 就把這些剩下的小數(shù)字一個(gè)個(gè)放到 nums1 前面空著的位置 j--; // 每放一個(gè)nums2 的指針往前走 k--; // 放的位置也往前走 } }圖解三指針工作過程初始狀態(tài)nums1 [1, 2, 3, 0, 0, 0] ↑ ↑ ↑ i | k | nums2 [2, 5, 6] ↑ jStep 1: 比較 nums1[i]3 和 nums2[j]6 → 6 更大 → 放到 k 位置nums1 [1, 2, 3, 0, 0, 6] ↑ ↑ ↑ i | k | nums2 [2, 5, 6] ↑ jStep 2: 比較 3 vs 5 → 5 更大nums1 [1, 2, 3, 0, 5, 6] ↑ ↑ ↑ i | k | nums2 [2, 5, 6] ↑ jStep 3: 比較 3 vs 2 → 3 更大nums1 [1, 2, 3, 3, 5, 6] ↑ ↑ ↑ i | k | nums2 [2, 5, 6] ↑ jStep 4: 比較 2 vs 2 → 相等放 nums2 的或 nums1 的也行nums1 [1, 2, 2, 3, 5, 6] ↑ ↑↑ i k nums2 [2, 5, 6] (j-1結(jié)束)此時(shí)j 0說明 nums2 已全部放入。而 nums1 剩下的 [1,2] 本來就在正確位置不用動(dòng) 注意如果 nums1 先耗盡i0但 nums2 還有剩就需要第二個(gè) while 循環(huán)把剩下的 nums2 元素補(bǔ)到前面。復(fù)雜度分析時(shí)間復(fù)雜度O(m n)每個(gè)元素最多被訪問一次總共 mn 個(gè)元素?？臻g復(fù)雜度O(1)只用了 i, j, k 三個(gè)變量沒有額外數(shù)組完美符合“原地合并”要求。為什么這個(gè)方法聰明利用了“有序”特性最大值一定在兩個(gè)數(shù)組的末尾。利用了“預(yù)留空間”從后往前寫不會(huì)踩到自己的腳。三指針分工明確i負(fù)責(zé) nums1 的有效數(shù)據(jù)j負(fù)責(zé) nums2 的所有數(shù)據(jù)k負(fù)責(zé)寫入位置三、結(jié)語算法之美在于洞察結(jié)構(gòu)這道題看似簡單卻完美展示了如何通過分析數(shù)據(jù)結(jié)構(gòu)特點(diǎn)有序 尾部空閑設(shè)計(jì)高效策略如何用極低的空間代價(jià)O(1)完成任務(wù)為什么時(shí)間復(fù)雜度 O(mn)是最優(yōu)的每個(gè)元素至少要看一次。下次遇到“合并有序數(shù)組”別再想著新建數(shù)組了試試從后往前三指針出擊記住好的算法不是代碼多炫而是恰到好處地利用已知條件。Happy Coding