算法入门Study（一）

一、时间复杂度

1.1 概念

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大的趋势

特点：

1.能够有效评估算法效率。 2.推算方法更简便。 3.存在一定局限性。

1.2 函数渐进界

函数渐进上界（最差时间复杂度）

复杂度由T(n)中最高的项来决定，忽略常数项、T(n)中的各种系数，使用大O记号表示。最实用，因为给出了一个效率安全值。

函数渐进下界（最佳时间复杂度）

用Ω记号表示

平均时间复杂度

体现算法在随机输入数据下的运行效率，用Θ表示

1.3 常见类型

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O (2ⁿ) < O(n!)

常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶

二、空间复杂度

2.1 概念

空间复杂度衡量算法占用内存空间随着数据量变大的增长趋势

算法相关空间：

输入空间：输入数据

暂存空间：暂存数据、栈帧空间、指令空间（统计范围）

输出空间：输出数据（统计范围）

2.2推算方法

（1）以最差输入数据为准

（2）以算法运行中的峰值内存为准

2.3 常见类型

O(1) < O(logn) < O(n) < O(n²) < O (2ⁿ)

常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶