目录
零，前言
一，时间复杂度的概念理解
二，时间复杂度的计算
三,常见的时间复杂度
1,常数阶
2,线性阶
3,对数阶
4,指数阶
5,根号阶
6,阶乘阶
零，前言
时间复杂度衡量着一个程序的好坏，时间复杂度的估算是算法题的重中之重。但是很多初学者对于时间复杂度缺少一种概念，对于复杂程序的估算难以理解，理解不了时间复杂度，算法学习无从下手。因此为了解决对时间复杂度的理解难题，本文将从简单到复杂介绍时间复杂度的计算方法，以及常见的时间复杂度，足以应付百分之八十的算法题。
一，时间复杂度的概念理解
一般来说要确定算法的运行时间，只有你将他拿到机器上去测试一下才能确定，但是过于麻烦，那么有没有一种方法能够估算该算法的运行时间呢？因此引入了时间复杂度这个概念。
时间复杂度是一种函数，定量地描述了该算法运行的时间。既然是一种函数，就涉及到自变量与因变量。因变量代表是时间复杂的规模，自变量是时间复杂度的执行时间。这里的执行时间并不是秒，分钟这类的具体时间 ，它表示的是一种“执行次数”。要想计算时间复杂度首先得找到该算法中的循环，算法中循环执行的次数就是算法的时间复杂度 。
算法的时间复杂度的具体表示为：用大写的 O 来体现算法时间复杂度如O（f（n）），称之为 大 O 记数法。
二，时间复杂度的计算
一，给定n个元素 的数组a[n]，求其中奇数有多少个。
判断一个数是偶数还是奇数，只需要求它除上 2 的余数是 0 还是 1，把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数器就是答案，需要遍历所有的数，因此代码为：
int count(int n, int a[]) {int cnt = 0;for(int i = 0; i < n; ++i) {if(a[i] % 2)++cnt;}return cnt;}
由代码段知，该函数中只有一层for循环，而该循环执行了n次，因此时间复杂度为O（N）；
二，求下面函数的时间复杂度
int fun(int n){int cnt = 0;for(int i = 0;i < n;i++){for(int j = 0; j<n; j++){cnt++; }}//两层循环，每次循环n次，因此为n*nfor(int k = 0; k<n; k++){++cnt;}//一层循环，循环n次for(int l = 0;l<10;l++){++cnt;}//一层循环，循环10次return cnt;}
由注释，可列出计算时间的复杂度的表达式：n*n +n +10。但是我们能写成O(N*N+N+10)吗？我们知道，对于时间复杂度我们不需算出精确的数字，只需要算出这个算法属于什么量级即可，我们又如何知道它属于哪个量级呢？即，我们将字母取无穷大，例如本题中字母为n，n取无穷大，而十对于n取无穷大后没有影响，因此10可以舍去，原表达式化为n*n+n，再简化为n*(n-1)，由于n为无穷大，因此-1也是没有影响的，原式就变成了O(N*N)。这就是大O渐近表示法，只是一种量级的估算，而不是准确的值。
由此可以得出计算时间复杂度的一般规律(用大O表示法)
1.去除表达式中所有加法常数
2.修改的表达式中只保留最高阶项,因为只有它对最终结果产生影响
3.如果最高阶项系数存在且不是1,则将其系数变为1,得出最后的表达式
三，计算冒泡排序的时间复杂度
void bubblesort(int* a,int n){assert(a);for(int end = n; end>0; end--){int exchange = 0;for(int i = 1; i<end; i++){if(a[i-1]>a[i]){swap(&a[i],&a[i-1]);exchange = 1;}}if(exchange==0)break;}}
例如在这个冒泡排序中,我们需要将无序数组转化为有序数组的一种算法,它并不像上题一样是简单的双层嵌套循环,很容易想到它的循环次数是一个等差数列,第一次循环n-1次,第二次n-2次.....一直到1.因此为n-1+n-2+n-3.....+1 = n*(n-1)/2,由上面所说的规律时间复杂度为O(N*N).
通过上面的例子我们看出,大O渐近表示法去掉了对结果影响不大的项,简洁明了地表示出了时间复杂度.在实际情况中一般只关注算法的最坏运行情况.
例如在上述冒泡排序中,如果给定的数组就已经是有序的了,那么就是它的最好情况,时间复杂度为O(N).但是如果有非常多的数据很显然我们看不出它到底是否为最好情况,所以我们必须用最坏的期望来计算所以它是O(N*N).
四,
int fun(int n){int i = 0;int cnt = 0;for( i; i<100;i++){cnt++;}return cnt;}
此时时间复杂度为O(1),这里的1不是指一次,而是常数次,该循环执行了100次,不管n多大,他都执行100次,所以是O(1).
三,常见的时间复杂度
1,常数阶
函数内循环为常数次或者没有循环,例如上面第四题,时间复杂度为O(1).
2,线性阶
就像上面第一题一样,只有一层循环,时间复杂度随n的增大线性增加,函数在图像上表示为一条经过原点的直线,O(N).
3,对数阶
例题:给定n 个元素的升序有序数组a[n] 和整数k，求 k在数组中的下标，不存在输出 -1。
这道题是经典的查找问题,一般最快的情况是使用二分查找
int binary(int n, int a[], int k) {int left = 0, right = n - 1;while(l <= r) {mid = (l + r)/2;if(a[mid] == k) return mid;else if(a[mid] < k)right = mid + 1;elseleft = mid + 1;}return -1;}
left和right指数组最左边和最右边的下标.每次将这个数组砍一半,求出mid中间下标. 由于是升序排列,如果中间下标代表的数大于给定的数k,那么k必定在中间下标的左边. 那么就将mid+1的值赋给right,反之则将mid+1的值赋给left,每次将数组砍一半直到找到数k为止.
n->n/2->n/4->n/8.....知道n变为1.
这个循环次数是对数的值,很显然是以二为底,数组个数n的对数O(log2n).
4,指数阶
指数阶一般是算法题的暴力解法,一般是多层循环的嵌套,例如上面题二中,最大是两层n次循环的嵌套因此`时间复杂度为O(N^2),n的平方次,要是三层n次循环的嵌套则为O(N^3).
5,根号阶
例题:给定一个数n,问n是否是一个素数.
常见的方法就是暴力法,n和每个小于n大于1的数相除如果都除不进,则n为素数.不过这次我们选择更为简单的方法例如:
bool isPrime(int n) {int i;if(n == 1) {return false;}int sqrtn = sqrt(n);for(int i = 2; i <= sqrtn; ++i) {if(n % i == 0) {return false;}}return true;}
只需要枚举所有小于根号n的数,使n与其相除,这样时间复杂度就小了很多.那为什么只需要枚举小于根号n个数呢?
因为假设n是数k的因子,那么n^2也必定是数k的因子,所以不需要枚举小于k这么多数,只需要枚举根号n个数就可以了.
6,阶乘阶
阶乘阶的讨论没有意义,阶乘级的时间复杂度一般在刷题时过不了,一般会用动态规划代替.
