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,否则返回阶乘