首頁>Club>
3
回覆列表
  • 1 # 使用者4753731016133

    其實如題主所說,他們本身是有意思,而且可以根據他們本身的意思去理解時間複雜度的概念。

    在數學上定義: 存在常數 c,使得當 N >= c 時 T(N) <= f(N),表示為 T(n) = O(f(n)) 。

    我們先從頭開始看:

    我們假設計算機執行一行基礎程式碼需要執行一次運算。

    那麼上面這個方法需要執行 2 次運算

    這個方法需要 (n + 1 + n + 1) = 2n + 2 次運算。

    我們把 演算法需要執行的運算次數 用 輸入大小n 的函式 表示,即 T(n) 。

    此時為了 估算演算法需要的執行時間 和 簡化演算法分析,我們引入時間複雜度的概念。

    數學上定義: 存在常數 c,使得當 N >= c 時 T(N) <= f(N),表示為 T(n) = O(f(n)) 。

    怎麼理解呢?

    如圖:

    當 N >= 2 的時候,f(n) = n^2 總是大於 T(n) = n + 2 的,於是我們說 f(n) 的增長速度是大於或者等於 T(n) 的,也說 f(n) 是 T(n) 的上界,可以表示為 T(n) = O(f(n))。

    因為f(n) 的增長速度是大於或者等於 T(n) 的,即T(n) = O(f(n)),所以我們可以用 f(n) 的增長速度來度量 T(n) 的增長速度,所以我們說這個演算法的時間複雜度是 O(f(n))。

    所以就有了我們現在理解的時間複雜度,記作: T(n) = O(f(n)),用來度量演算法的執行時間。它表示隨著 輸入大小n 的增大,演算法執行需要的時間的增長速度可以用 f(n) 來描述。

    顯然如果 T(n) = n^2,那麼 T(n) = O(n^2),T(n) = O(n^3),T(n) = O(n^4) 都是成立的,但是因為第一個 f(n) 的增長速度與 T(n) 是最接近的,所以第一個是最好的選擇,所以我們說這個演算法的複雜度是 O(n^2) 。

    補充:

    上述例子中

    這個方法需要 (n + 1 + n + 1) = 2n + 2 次運算,此時 T(n) = 2n + 2。那麼按照上述 大O 的數學定義T(n) = O(n),T(n) = O(n^2),T(n) = O(n^3) 都是成立的,但是因為第一個 f(n) 的增長速度與 T(n) 是最接近的,所以第一個是最好的選擇,所以這個演算法的複雜度是 O(n) 。

    可以參考 十分鐘從零搞定時間複雜度

  • 中秋節和大豐收的關聯?
  • 水深天熱魚兒不吃鉤,水淺草多又該如何釣魚?