Python 技術手冊 第三版

最佳化

|

541

時間因此正比於

1+2+3+...N-1

，其總和值為

O(N

2

)

。因此，

slow

的總執行時

間為

O(N

2

)

。

以一個

O(N)

的解法取代

O(N

2

)

的解法幾乎總是值得的，除非你能以某種

方式為輸入大小

N

設下嚴格的小值限制。如果

N

的增長沒有非常嚴格的界

限，那麼最後大型的

N

值會讓

O(N

2

)

的解法比

O(N)

的解法慢非常多，不管

每個情況中的比例常數為何（也不管效能側寫告訴了你什麼）。除非其他

地方有你無法消除的其他

O(N

2

)

或更糟的瓶頸，程式中那個是

O(N

2

)

的部分

就會是程式的主要瓶頸，占據了大型

N

值大部分的執行時間。幫你自己一

個忙，留意這種 big O：所有其他的效能議題，相較之下，通常幾乎都可以

算是無關緊要。

順便提一下，你還可以讓函式

fast

變得更快，方法是用 Python 的慣用語

來表達它。只需以下列這單一個述句取代頭兩行：

result = list(it)

這個變更不會影響到

fast

的 big-O 特徵（

fast

在變更後仍為

O(N)

），但會

以一個很大的常數倍數加速執行。

簡單比複雜好，通常也比較快！

在 Python 中，常見的情形是，表達事情的時候，最簡單、

最清楚、最直接且慣用語式（idiomatic）的方式也會是最

快的。

在 Python 中，挑選 big-O 好的演算法的工作大致就跟在任何其他語言中相

同。你只需要 Python 基本構建組塊（building blocks）的 big-O 效能相關

的幾個線索，而我們會在接下來的章節提供它們。

串列作業

Python 的串列在內部實作為 ...