算法的效率一般指算法的運行時間。
算法效率的度量方法睡扬。
- 算法采用的策略盟蚣、方案
- 編譯產生的代碼質量
- 問題的輸入規(guī)模
- 機器執(zhí)行指令的速度
函數的漸近增長
給定兩個函數 f(n) 和 g(n)卖怜，如果存在一個整數N屎开，使得對于所有的n>N, f(n) 中總是比 g(n) 大，那么牍戚，我們說 f(n) 的增長漸近快于 g(n)
image.png
image.png
算法可以忽略一些加法常數
image.png
image.png
與最高次項相乘的常數并不重要
image.png
image.png
最高次項指數大的，函數隨著n的增長如孝，結果也會變得增長特別快
image.png
image.png
image.png
判斷一個算法的效率時，函數中的常數項和其他次要項常车谖可以忽略锁孟，二更應該關注主項（最高項）的階數茁瘦。
空間復雜度 時間復雜度
image.png
推導大O階方法
- 用常數1取代運行次數函數中的所有加法常數
- 在修改后的運行次數函數中品抽，只保留最高階項
- 如果最高項存在且不是1，則去除與這個項相乘的常數
image.png
線性階
一般含有非嵌套循環(huán)涉及線性階圆恤，線性階就是隨著問題規(guī)模 n 的擴大，對應計算次數呈直線增長腔稀。
平方階
n^2
對數階
image.png
image.png
image.png
image.png
image.png
最壞情況與平均情況
image.png
通常除非特別指定，我們提到的運行時間都是最壞情況的運行時間焊虏。
算法的控件復雜度
image.png
