一、前言
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别
衡量不同算法之间的优劣主要是通过时间和空间两个维度去考量:
- 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
- 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述
通常会遇到一种情况,时间和空间维度不能够兼顾,需要在两者之间取得一个平衡点是我们需要考虑的
一个算法通常存在最好、平均、最坏三种情况,我们一般关注的是最坏情况
最坏情况是算法运行时间的上界,对于某些算法来说,最坏情况出现的比较频繁,也意味着平均情况和最坏情况一样差
二、时间复杂度
时间复杂度是指执行这个算法所需要的计算工作量,其复杂度反映了程序执行时间「随输入规模增长而增长的量级」,在很大程度上能很好地反映出算法的优劣与否
一个算法花费的时间与算法中语句的「执行次数成正比」,执行次数越多,花费的时间就越多
算法的复杂度通常用大O符号表述,定义为T(n) = O(f(n))
,常见的时间复杂度有:O(1)常数型、O(log n)对数型、O(n)线性型、O(nlogn)线性对数型、O(n^2)平方型、O(n^3)立方型、O(n^k)k次方型、O(2^n)指数型,如下图所示: