對于一個特定的問題,采用的數據結構不同,其設計的算法一般也不同,即使在同一種數據結構下,也可以采用不同的算法。那么,對于解決同一問題的不同算法,選擇哪一種算法比較合適,以及如何對現有的算法進行改進,從而設計出更適合于數據結構的算法,這就是算法效率的度量問題。評價一個算法優劣的主要標準如下:
1. 正確性(Correctness)算法的執行結果應當滿足預先規定的功能和性能的要求,這是評價一個算法的最重要,也是最基本的標準。算法的正確性還包括對于輸入、輸出處理的明確而無歧義的描述。
2. 可讀性(Readability)算法主要是為了人閱讀和交流,其次才是機器的執行。所以,一個算法應當思路清晰,層次分明,簡單明了,易讀易懂。即使算法已轉變成機器可執行的程序,也需要考慮人能較好地閱讀理解。同時,一個可讀性強的算法也有助于對算法中隱藏錯誤的排除和算法的移植;
3. 健壯性(Robustness)一個算法應該具有很強的容錯能力,當輸入不合法的數據時,算法應當能做適當的處理,使得不至于引起嚴重的后果。健壯性要求表明算法要全面細致地考慮所有可能出現的邊界情況和異常情況,并對這些邊界情況和異常情況做出妥善的處理,盡可能使算法沒有意外的情況發生。
4. 運行時間(Running Time)運行時間是指算法在計算機上運行所花費的時間,它等于算法中每條語句執行時間的總和。對于同一個問題如果有多個算法可供選擇,應盡可能選擇執行時間短的算法。一般來說,執行時間越短,性能越好;
5. 占用空間(Storage Space)占用空間是指算法在計算機上存儲所占用的存儲空間,算法占用的存儲空間是指算法執行過程中所需要的最大存儲空間,對于一個問題如果有多個算法可供選擇,應盡可能選擇存儲量需求低的算法
- 基礎
- 數據
- 數據元素
- 數據結構
- 集合結構
- 線性結構
- 樹型結構
- 圖狀結構
- 數據存儲結構
- 算法定義
- 算法效率度量
- 算法效率分析
- 時間復雜度
- O(1)
- O(n)
- O(n2)
- O(logn)
- 空間復雜度
- 線性表
- 數組
- 鏈表
- 串矩陣和廣義表
- 串
- 矩陣
- 廣義表
- 棧和隊列
- 棧
- 隊列
- 樹和二叉樹
- 二叉樹
- 滿二叉樹
- 完全二叉樹
- 哈夫曼樹
- 二叉查找樹-BST樹
- AVL樹
- 紅黑樹
- B樹
- B+樹
- 字典樹
- 跳表
- 算法
- 排序算法
- 冒泡排序
- 選擇排序
- 快速排序
- 插入排序
- 希爾排序
- 歸并排序
- 堆排序
- 基數排序
- 計數排序
- 桶排序
- 查找算法
- 二分查找算法
- Hash算法
- 一致性hash算法
- 算法題
- 001-用兩個棧實現隊列
- 002-只使用棧和遞歸逆序一個棧
- 附錄
- SkipList跳表