王道计算机考研 数据结构

算法效率——时间复杂度（事前预估T(n)与n的关系）

例子：

1、逐步递增

问题规模 n

while循环② 条件判断——n+1次；③④ 计算——n次

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

二、嵌套循环型

在while循环中插入一个for循环

外层循环——while循环，n次

内层循环——for循环，n²次

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

结论：

1、顺序执行的代码可以忽略

2、只需分析一个基本操作，分析其执行次数 f(n) 和问题规模 n 的关系

3、多层嵌套循环，只关注最深层循环

三、指数递增型

T(n) = O（x）

四、搜索数字型

输入一个长度为n的数组，乱序存放了1~n，从第一个元素开始找到元素n。

根据输入的flag数组n不一样，循环次数x不一样。

需考虑不同情况：

1、最好时间复杂度：n在第一个 T(n) = O (1)

2、最坏时间复杂度：n在最后 T(n) = O (n)

3、平均时间复杂度：设元素n出现在任意位置的概率都为n/1

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

T(n) = O(n)

、