如何計算Python函數的算法複雜度？

Question

當需要顯示算法的有效性時，我們需要顯示函數的算法複雜性 - Big O等等。在Python代碼中，我們如何顯示或計算函數的界限？

Answer 1

一般情況下，沒有辦法以編程方式執行此操作（遇到暫停問題）。

如果您不知道從哪裏開始，可以通過運行一些基準（例如使用time模塊）和各種大小的輸入來了解功能如何執行。您甚至可以收集足夠的數據以形成懷疑關於運行時可能是什麼。但這不會給你一個嚴格的答案 - 爲此，你需要以數學方式證明你的可疑界限事實上是真的。

舉例來說，如果我打了排序功能，並觀察時間大致比例增加，以輸入尺寸的平方，我可能嫌疑了這種複雜性是O(n**2)。但這並不構成證據 - 特別是在典型輸入下運行良好的一些算法具有導致性能很差的病理輸入。

爲了證明這個界限實際上是O(n**2)，我需要看看算法在最壞的情況下做了什麼 - 在這個例子中，我可能會分析一個選擇排序，它會重複掃描整個未排序部分該清單並挑選最低的未分類號碼。很明顯，我正在檢查像n*(n-1) == O(n**2)元素。如果檢查元素是一個常量操作，並且將最後一個元素放在正確的位置也不會比O(n**2)差，那麼我的整個算法就是O(n**2)。

Answer 2

看看大O符號的各種蟒蛇操作位置：

https://wiki.python.org/moin/TimeComplexity

這是一個很好的複習，爲高校的東西，以及：

http://www.nikhilgopal.com/2012/04/refresher-on-big-o-notation-python.html

最後一個很好的具體例子：

Python complexity (run-time)

Answer 3

如果您試圖爲自己的函數獲取大O符號，則可能需要變量來跟蹤諸如以下內容的變量： runTime;比較者的數量;迭代次數;等等。以及一些計算調查這些如何對應於您的數據的大小。 這可能是最好的手動先做，所以你可以檢查你對算法的理解。