跳轉至

小結

重點回顧

演算法效率評估

  • 時間效率和空間效率是衡量演算法優劣的兩個主要評價指標。
  • 我們可以透過實際測試來評估演算法效率,但難以消除測試環境的影響,且會耗費大量計算資源。
  • 複雜度分析可以消除實際測試的弊端,分析結果適用於所有執行平臺,並且能夠揭示演算法在不同資料規模下的效率。

時間複雜度

  • 時間複雜度用於衡量演算法執行時間隨資料量增長的趨勢,可以有效評估演算法效率,但在某些情況下可能失效,如在輸入的資料量較小或時間複雜度相同時,無法精確對比演算法效率的優劣。
  • 最差時間複雜度使用大 \(O\) 符號表示,對應函式漸近上界,反映當 \(n\) 趨向正無窮時,操作數量 \(T(n)\) 的增長級別。
  • 推算時間複雜度分為兩步,首先統計操作數量,然後判斷漸近上界。
  • 常見時間複雜度從低到高排列有 \(O(1)\)\(O(\log n)\)\(O(n)\)\(O(n \log n)\)\(O(n^2)\)\(O(2^n)\)\(O(n!)\) 等。
  • 某些演算法的時間複雜度非固定,而是與輸入資料的分佈有關。時間複雜度分為最差、最佳、平均時間複雜度,最佳時間複雜度幾乎不用,因為輸入資料一般需要滿足嚴格條件才能達到最佳情況。
  • 平均時間複雜度反映演算法在隨機資料輸入下的執行效率,最接近實際應用中的演算法效能。計算平均時間複雜度需要統計輸入資料分佈以及綜合後的數學期望。

空間複雜度

  • 空間複雜度的作用類似於時間複雜度,用於衡量演算法佔用記憶體空間隨資料量增長的趨勢。
  • 演算法執行過程中的相關記憶體空間可分為輸入空間、暫存空間、輸出空間。通常情況下,輸入空間不納入空間複雜度計算。暫存空間可分為暫存資料、堆疊幀空間和指令空間,其中堆疊幀空間通常僅在遞迴函式中影響空間複雜度。
  • 我們通常只關注最差空間複雜度,即統計演算法在最差輸入資料和最差執行時刻下的空間複雜度。
  • 常見空間複雜度從低到高排列有 \(O(1)\)\(O(\log n)\)\(O(n)\)\(O(n^2)\)\(O(2^n)\) 等。

Q & A

Q:尾遞迴的空間複雜度是 \(O(1)\) 嗎?

理論上,尾遞迴函式的空間複雜度可以最佳化至 \(O(1)\) 。不過絕大多數程式語言(例如 Java、Python、C++、Go、C# 等)不支持自動最佳化尾遞迴,因此通常認為空間複雜度是 \(O(n)\)

Q:函式和方法這兩個術語的區別是什麼?

函式(function)可以被獨立執行,所有參數都以顯式傳遞。方法(method)與一個物件關聯,被隱式傳遞給呼叫它的物件,能夠對類別的例項中包含的資料進行操作。

下面以幾種常見的程式語言為例來說明。

  • C 語言是程序式程式設計語言,沒有物件導向的概念,所以只有函式。但我們可以透過建立結構體(struct)來模擬物件導向程式設計,與結構體相關聯的函式就相當於其他程式語言中的方法。
  • Java 和 C# 是物件導向的程式語言,程式碼塊(方法)通常作為某個類別的一部分。靜態方法的行為類似於函式,因為它被繫結在類別上,不能訪問特定的例項變數。
  • C++ 和 Python 既支持程序式程式設計(函式),也支持物件導向程式設計(方法)。

Q:圖解“常見的空間複雜度型別”反映的是否是佔用空間的絕對大小?

不是,該圖展示的是空間複雜度,其反映的是增長趨勢,而不是佔用空間的絕對大小。

假設取 \(n = 8\) ,你可能會發現每條曲線的值與函式對應不上。這是因為每條曲線都包含一個常數項,用於將取值範圍壓縮到一個視覺舒適的範圍內。

在實際中,因為我們通常不知道每個方法的“常數項”複雜度是多少,所以一般無法僅憑複雜度來選擇 \(n = 8\) 之下的最優解法。但對於 \(n = 8^5\) 就很好選了,這時增長趨勢已經佔主導了。