Java數據結構應用——算法的效率

2019-11-17 04:03:42

字體：大中小

來源：轉載

供稿：網友

對于該節的學習，還有待深入理解：

上總結：

1.測定一個算法的運行時間的最可靠方法就是計數它所執行的基本操作的數量，運行時間與這個計數結果成正比。

2.為了分析一個程序的運行時間，重要的是把這個程序看成與實現它的程序設計語言無關的算法。并分析這個算法。

3.把一個算法的基本操作的技術表示成輸入規模變量的函數

4.給定兩個函數f(n)和g(n)，如果存在一個整數N，使得對于所有的n>N,f(n)總是比g(n)大，那么說f(n)的增長漸進快于g(n)。

5.算法運行時間的大O階獲得步驟：

  stap1.用常數1取代運行時間中的所有加法常數。

  stap2.在修改后的運行時間中，只保留最高階項。n

  stap3.如果最高階項不是1，（如果有的話）去除與這個相乘的常數。

6.若干典型的運行時間階是：O(1)(常數階)，O(n)(線性階)，O(n平方)(二次階)，O(n立方)(三次階)，O(n log n)，O(log n)(對數階)，

O(k n次方)(指數階)。

排列后： 1 < log n < n < nlogn < n平方 < n立方 < k n次方

7.對于一個算法，可以把獨立分析出來的它的不同組件的運行時間相加，得到這個算法本身的運行時間。

8.對于川縣在算法輸入規模中的每一個變量，運行時間函數中至多有一項包含該變量。

9.算法的最壞情況運行實際那保證運行時間不會變的更壞。

10.算法的平均運行時間是平均可以期待的運行時間。通常很難通過分析確定算法的平均運行時間。

11.時間復雜度指的是運行時間需求，而空間復雜度值得是空間需求。

12.無限定詞的復雜度通常指的是時間復雜度。

13.如果沒有明示最壞or平均情況復雜度，則通常指最壞情況復雜度。

14.一個算法的空間需求總是小于或等于它的時間需求。

上一篇：java中的一個MyPoint方法

下一篇：Java Media Framework 基礎教程