如何用JavaScript學(xué)習(xí)算法復(fù)雜度

本篇內(nèi)容介紹了“如何用JavaScript學(xué)習(xí)算法復(fù)雜度”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

在本文中，我們將探討 “二次方” 和 “n log(n)” 等術(shù)語在算法中的含義。

在后面的例子中，我將引用這兩個數(shù)組，一個包含 5 個元素，另一個包含 50 個元素。我還會用到 JavaScript 中方便的 performance  API 來衡量執(zhí)行時間的差異。

const smArr = [5, 3, 2, 35, 2];  const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2];

什么是 Big O 符號?

Big O 表示法是用來表示隨著數(shù)據(jù)集的增加，計(jì)算任務(wù)難度總體增長的一種方式。盡管還有其他表示法，但通常 big O  表示法是最常用的，因?yàn)樗塾谧顗牡那闆r，更容易量化和考慮。最壞的情況意味著完成任務(wù)需要最多的操作次數(shù);如果你在一秒鐘內(nèi)就能恢復(fù)打亂魔方，那么你只擰了一圈的話，不能說自己是做得最好的。

當(dāng)你進(jìn)一步了解算法時，就會發(fā)現(xiàn)這非常有用，因?yàn)樵诶斫膺@種關(guān)系的同時去編寫代碼，就能知道時間都花在了什么地方。

當(dāng)你了解更多有關(guān) Big O 表示法的信息時，可能會看到下圖中不同的變化。我們希望將復(fù)雜度保持在盡可能低的水平，最好避免超過 O(n)。

O(1)

這是理想的情況，無論有多少個項(xiàng)目，不管是一個還是一百萬個，完成的時間量都將保持不變。執(zhí)行單個操作的大多數(shù)操作都是  O(1)。把數(shù)據(jù)寫到數(shù)組、在特定索引處獲取項(xiàng)目、添加子元素等都將會花費(fèi)相同的時間量，這與數(shù)組的長度無關(guān)。

const a1 = performance.now(); smArr.push(27); const a2 = performance.now(); console.log(`Time: ${a2 - a1}`); // Less than 1 Millisecond   const b1 = performance.now(); bigArr.push(27); const b2 = performance.now(); console.log(`Time: ${b2 - b1}`); // Less than 1 Millisecond

O(n)

在默認(rèn)情況下，所有的循環(huán)都是線性增長的，因?yàn)閿?shù)據(jù)的大小和完成的時間之間存在一對一的關(guān)系。所以如果你有 1,000 個數(shù)組項(xiàng)，將會花費(fèi)的 1,000  倍時間。

const a1 = performance.now(); smArr.forEach(item => console.log(item)); const a2 = performance.now(); console.log(`Time: ${a2 - a1}`); // 3 Milliseconds  const b1 = performance.now(); bigArr.forEach(item => console.log(item)); const b2 = performance.now(); console.log(`Time: ${b2 - b1}`); // 13 Milliseconds

O(n^2)

指數(shù)增長是一個陷阱，我們都掉進(jìn)去過。你是否需要為數(shù)組中的每個項(xiàng)目找到匹配對?將循環(huán)放入循環(huán)中是一種很好的方式，可以把 1000  個項(xiàng)目的數(shù)組變成一百萬個操作搜索，這將會使你的瀏覽器失去響應(yīng)。與使用雙重嵌套循環(huán)進(jìn)行一百萬次操作相比，最好在兩個單獨(dú)的循環(huán)中進(jìn)行 2,000 次操作。

const a1 = performance.now(); smArr.forEach(() => {     arr2.forEach(item => console.log(item)); }); const a2 = performance.now(); console.log(`Time: ${a2 - a1}`); // 8 Milliseconds   const b1 = performance.now(); bigArr.forEach(() => {     arr2.forEach(item => console.log(item)); }); const b2 = performance.now(); console.log(`Time: ${b2 - b1}`); // 307 Milliseconds

O(log n)

我認(rèn)為關(guān)于對數(shù)增長比較好的比喻，是想象在字典中查找像 “notation” 之類的單詞。你不會在一個詞條一個詞條的去進(jìn)行搜索，而是先找到 “N”  這一部分，然后是 “OPQ” 這一頁，然后按字母順序搜索列表直到找到匹配項(xiàng)。

通過這種“分而治之”的方法，找到某些內(nèi)容的時間仍然會因字典的大小而改變，但遠(yuǎn)不及 O(n)  。因?yàn)樗鼤诓徊榭创蟛糠謹(jǐn)?shù)據(jù)的情況下逐步搜索更具體的部分，所以搜索一千個項(xiàng)目可能需要少于 10 個操作，而一百萬個項(xiàng)目可能需要少于 20  個操作，這使你的效率最大化。

在這個例子中，我們可以做一個簡單的 快速排序。

const sort = arr => {   if (arr.length < 2) return arr;    let pivot = arr[0];   let left = [];   let right = [];    for (let i = 1, total = arr.length; i < total; i++) {     if (arr[i] < pivot) left.push(arr[i]);     else right.push(arr[i]);   };   return [     ...sort(left),     pivot,     ...sort(right)   ]; }; sort(smArr); // 0 Milliseconds sort(bigArr); // 1 Millisecond

O(n!)

最糟糕的一種可能性是析因增長。最經(jīng)典的例子就是旅行的推銷員問題。如果你要在很多距離不同的城市之間旅行，如何找到在所有城市之間返回起點(diǎn)的最短路線?暴力方法將是檢查每個城市之間所有可能的路線距離，這是一個階乘并且很快就會失控。

由于這個問題很快會變得非常復(fù)雜，因此我們將通過簡短的遞歸函數(shù)演示這種復(fù)雜性。這個函數(shù)會將一個數(shù)字去乘以函數(shù)自己，然后將數(shù)字減去1。階乘中的每個數(shù)字都會這樣計(jì)算，直到為  0，并且每個遞歸層都會把其乘積添加到原始數(shù)字中。

階乘只是從 1 開始直至該數(shù)字的乘積。那么 6!是 1x2x3x4x5x6 = 720。

const factorial = n => {   let num = n;    if (n === 0) return 1   for (let i = 0; i < n; i++) {     num = n * factorial(n - 1);   };    return num; }; factorial(1); // 2 Milliseconds factorial(5); // 3 Milliseconds factorial(10); // 85 Milliseconds factorial(12); //  11,942 Milliseconds

我原本打算顯示 factorial(15)，但是 12 以上的值都太多，并且使頁面崩潰了，這也證明了為什么需要避免這種情況。

“如何用JavaScript學(xué)習(xí)算法復(fù)雜度”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！