算法效率——時間復雜度（事前預估T(n)與n的關系）

例子：

1、逐步遞增

問題規(guī)模 n

while循環(huán)② 條件判斷——n+1次；③④ 計算——n次

T(n) = O(f(n)) = n

二、嵌套循環(huán)型

在while循環(huán)中插入一個for循環(huán)

外層循環(huán)——while循環(huán)，n次

內層循環(huán)——for循環(huán)，n2次

T(n）=O(n)+ O(n2) = O(n2)

結論：

1、順序執(zhí)行的代碼可以忽略

2、只需分析一個基本操作，分析其執(zhí)行次數(shù) f(n) 和問題規(guī)模 n 的關系

3、多層嵌套循環(huán)，只關注最深層循環(huán)

三、指數(shù)遞增型

T(n) = O（x）

四、搜索數(shù)字型

輸入一個長度為n的數(shù)組，亂序存放了1~n，從第一個元素開始找到元素n。

根據(jù)輸入的flag數(shù)組n不一樣，循環(huán)次數(shù)x不一樣。

需考慮不同情況：

1、最好時間復雜度：n在第一個 T(n) = O (1)

2、最壞時間復雜度：n在最后 T(n) = O (n)

3、平均時間復雜度：設元素n出現(xiàn)在任意位置的概率都為n/1

x = （1+2+3+…n）*1/n = (1+n)/2

T(n) = O(n)

、