其實如題主所說,他們本身是有意思,而且可以根據他們本身的意思去理解時間複雜度的概念。
在數學上定義: 存在常數 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) 。
可以參考 十分鐘從零搞定時間複雜度
其實如題主所說,他們本身是有意思,而且可以根據他們本身的意思去理解時間複雜度的概念。
在數學上定義: 存在常數 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) 。
可以參考 十分鐘從零搞定時間複雜度