演算法速度慢

❶ 如何衡量一個演算法的快慢

如何衡量一個演算法的快慢
用具體的操作數來衡量

當我們說衡量一個演算法的快慢時，我們是希望找到一種方便的統一標准，使得對於同一個演算法，我們的衡量標准不會受到一些不重要的因素影響而保持一致；對於不同的演算法，我們能夠比較它們的優劣並在實際的應用中進行選擇。

一個自然的想法是測量這個演算法運行所需要的時間，然後選擇跑得快的演算法。但是不同的機器運行的速度是不一樣的，一個同樣的演算法在不同機器上測出來的時間可能非常不同。而且，每次想要知道一個演算法的快慢如果都要在機器上通過計時來測量的話，是一件非常痛苦的事情，因為有些演算法可能一次要跑上一天，一個月，甚至一個世紀。

一個有效的替代方法是通過計算一個演算法用了多少次操作（或者說運算量）來衡量它運行的快慢，比如用了多少次加減法，乘除法，函數調用和賦值等操作。操作數越多，運行的所需要的時間就越多。這樣的一種想法保證了我們對演算法的衡量不會因為測試環境的變化而變化，也不用通過實際運行來測量，只需通過計算就能得到操作數的數量。

用函數來衡量

僅僅計算操作數的一個問題是：一個固定的演算法，針對不同的輸入規模，它所需要的操作數量是不一樣的。比如一個排序的演算法，排100個數字和排10000個數字相比，排10000個數字所需要的運算量會大很多。也就是，操作數是隨輸入規模變化的一個函數。

所以，我們假如輸入規模是n，那麼操作數就是f(n)。有時候，輸入規模不只有一個，比如關於一個矩陣的演算法需要的操作數，可能和矩陣的長和寬都有關系，這時候，ff就變成了一個關於長和寬的二元函數，比如f(w,h)。這種擴展是合理的，但是為了討論方便，我們先只考慮規模只是一個變數n的情況。