[[431020]]

 算法是問題的解決步驟，同一個問題可以有多種解決思路，也就會有多種算法，但是算法之間是有好壞之分的，區(qū)分標(biāo)志就是復(fù)雜度。

通過復(fù)雜度可以估算出耗時/內(nèi)存占用等性能的好壞，所以我們用復(fù)雜度來評價算法。

(不了解復(fù)雜度可以看這篇：性能分析不一定得用 Profiler，復(fù)雜度分析也行)

開發(fā)的時候，大多數(shù)場景下我們用最樸素的思路，也就是復(fù)雜度比較高的算法也沒啥問題，好像也用不到各種高大上的算法，算法這個東西似乎可學(xué)可不學(xué)。

其實(shí)不是的，那是因?yàn)槟銢]有遇到一些數(shù)據(jù)量大的場景。

下面我給你舉一個我之前公司的具體場景的例子：

體現(xiàn)算法威力的例子

這是我前公司高德真實(shí)的例子。

我們會做全源碼的依賴分析，會有幾萬個模塊，一個模塊依賴另一個模塊叫做正向依賴，一個模塊被另一個模塊依賴叫做反向依賴。我們會先分析一遍正向依賴，然后再分析一遍反向依賴。

分析反向依賴的時候，之前的思路是這樣的，對于每一個依賴，都遍歷一邊所有的模塊，找到依賴它的模塊，這就是它的反向依賴。

這個思路是很樸素的，容易想到的思路，但是這個思路有沒有問題呢?

這個算法的復(fù)雜度是 O(n^2)，如果 n 達(dá)到了十幾萬，那性能會很差的，從復(fù)雜度我們就可以估算出來。

事實(shí)上也確實(shí)是這樣，后來我們跑一遍全源碼依賴需要用 10 幾個小時，甚至一晚上都跑不出來。

如果讓你去優(yōu)化，你會怎么優(yōu)化性能呢?

有的同學(xué)可能會說，能不能拆成多進(jìn)程/多個工作線程，把依賴分析的任務(wù)拆成幾部分來做，這樣能得到幾倍的性能提升。

是，幾倍的提升很大了。

但是如果說我們后來做了一個改動，性能直接提升了幾萬倍你信么?

我們的改動方式是這樣的：

之前是在分析反向依賴的時候每一個依賴都要遍歷一遍所有的正向依賴。但其實(shí)正向依賴反過來不就是反向依賴么?

所以我們直接改成了分析正向依賴的時候同時記錄反向依賴。

這樣根本就不需要單獨(dú)分析反向依賴了，算法復(fù)雜度從 O(n^2)降到了 O(n)。

O(n^2) 到 O(n) 的變化在有幾萬個模塊的時候，就相當(dāng)于幾萬倍的性能提升。

這體現(xiàn)在時間上就是我們之前要跑一個晚上的代碼，現(xiàn)在十幾分鐘就跑完了。這優(yōu)化力度，你覺得光靠多線程/進(jìn)程來跑能做到么?

這就是算法的威力，當(dāng)你想到了一個復(fù)雜度更低的算法，那就意味著性能有了大幅的提升。

就像為什么我們整天說 diff 算法，因?yàn)樗?O(n^2) 的樸素算法復(fù)雜度降低到了 O(n)，這就意味著 dom 節(jié)點(diǎn)有幾千個的時候，就會有幾千倍的性能提升。

所以，感受到算法的威力了么?

總結(jié)

多線程、緩存等手段最多提升幾倍的性能，而算法的優(yōu)化是直接提升數(shù)量級的性能，當(dāng)數(shù)據(jù)量大了以后，就是幾千幾萬倍的性能提升。

那為什么我們平時覺得算法沒用呢?那是因?yàn)槟闾幚淼臄?shù)據(jù)量太小了，處理幾百個數(shù)據(jù)，你用 O(n^2) O(n^3) 和 O(n) 的算法，都差不了多少。

你處理的場景數(shù)據(jù)量越大，那算法的重要性越高，因?yàn)楹玫乃惴ê筒畹乃惴ǖ牟顒e不是幾倍幾十倍那么簡單，可能是幾萬倍的差別。

所以，你會見到各大公司都在考算法，沒用么?不是的，是太過重要了，可以說決定著寫出的代碼的性能。