时间复杂度精讲

1、什么是时间复杂度和空间复杂度

1.1算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。

时间效率被称为时间复杂度，二空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，二空间复杂度主要衡量的一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

1.2时间复杂度的概念

算法中的基本操作的执行次数，为算法的时间复杂度。

引例：

时间复杂度是一个估算，是去看表达式中影响最大的那一项（最高阶）

所以最终的结果是O（n^2）

计算方式：

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么我们采用大O的渐进表示法。

推导方法：

1、用常数1取代运行时间中的所有加法常数。

2、只保留最高阶项。

3、如果最高阶项存在且不是1，则去除这个项目相乘的系数。

实例1：

O（n）

实例2：

实例3：

确定的常数次，都是O（1）！

实例4：

分情况讨论，做最坏的打算。

实例5：冒泡排序

实例6：二分查找（logn ）

实例6：阶乘递归

三目操作符：表示有3个操作数，N<2吗，若小于就返回N，否则返回阶乘