如何计算一个算法的时间复杂度？
算这个时间复杂度实际上只需要遵循如下守则：
用常数1来取代运行时间中所有加法常数；
只要高阶项，不要低阶项；
不要高阶项系数；
1:常见的时间复杂度：
按增长量级递增排列，常见的时间复杂度有：
O(1)—常数阶
O(N)—线性阶
O(log2N)—对数阶
O(nlogn)—线性对数阶
O(n^2)—平方阶
1.1:O(1)—常数阶
O(1)的算法是一些运算次数为常数的算法。例如：
temp=a;
a=b;
b=temp;
根据守则：
用常数1来取代运行时间中所有加法常数；
上面语句共三条操作，单条操作的频度为1，即使他有成千上万条操作，也只是个较大常数，这一类的时间复杂度为O(1)；
1.2:O(N)—线性阶
O(n)的算法是一些线性算法。例如：
sum=0；
for(i=0;i<n;i++)
sum++；
上面代码中第一行频度1，第二行频度为n，第三行频度为n，所以f(n)=n+n+1=2n+1。
根据守则：
只要高阶项，不要低阶项目，常数项置为1，去除高阶项的系数：
所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。
1.3:O(log2N)—对数阶
什么是对数?
a^x = N,(a>0 && a!=1),那么x即是以a为底，N的对数，记作
其中a叫做对数的底数，N叫做真数。
例1:
private static void 对数阶() {
int number = 1;//执行1次
int n = 100;//执行1次
while (number < n) {
number = number * 2; // 执行n/2次
System.out.println("哈哈");//执行1次
}
}
假设n为100，number是1，小于100退出循环。
第1次循环，number = 2，2^1。
第2次循环，number = 4, 2^2。
第3次循环，number = 8, 2^3。
第x次循环，number = 2^x
也就是2^x=n得出x=log₂n。因此它的复杂度为O(logn)。
例2:
二分查找；
比如: 1,3,5,6,7,9；找出7
如果全部遍历时间频度为n；
二分查找每次砍断一半，即为n/2；
随着查询次数的提升，频度变化作表：
查询次数 时间频度
1 n/2
2 n/2^2
3 n/2^3
k n/2^k
当最后找到7的时候时间频度则是1；
也就是:
n/2^k = 1;
n = 2^k；
k则是以2为底，n的对数，就是Log2N；
那么二分查找的时间复杂度就是O(Log2N)；
1.4:O(nlogn)—线性对数阶
上面看了二分查找，是LogN的（LogN没写底数默认就是Log2N)；
线性对数阶就是在LogN的基础上多了一个线性阶；
比如这么一个算法流程：
数组a和b，a的规模为n，遍历的同时对b进行二分查找，如下代码：
for(int i =0;i<n;i++)
binary_search(b);
}
1.5:O(n^2)—平方阶
普通嵌套循环
private static void 普通平方阶(){
int n = 100;
for (int i = 0; i < n; i++) {//执行n次
for (int j = 0; j < n; j++) {//执行n次
System.out.println("哈哈");
}
}
}
这种就是2层循环嵌套起来，都是执行n次，属于乘方关系，它的时间复杂度为O(n^2)。
等差数列嵌套循环
private static void 等差数列平方阶() {
int n = 100;
for (int i = 0; i < n; i++) {//执行n次
for (int j = i; j < n; j++) {//执行n - i次
System.out.println("哈哈");
}
}
}
基本式：
i = 0，循环执行次数是 n 次。
i = 1，循环执行次数是 n-1 次。
i = 2，循环执行次数是 n-2 次。
…
i = n-1，循环执行的次数是 1 次。
换算式：
result = n + (n - 1) + (n - 2) … + 1
被加数递减，抽象为一个等差数列求n项和的问题，公差为1，带入公式，Sn = n(a1 + an ) ÷2
result = (n(n+1))/2
result = (n^2+n)/2
result = (n^2)/2 + n/2
粗略计算时间复杂度的三部曲：
1.去掉运行时间中的所有加法常数。
没有加法常数，不考虑。
2.只保留最高阶项。
最高阶参考上面列出的按增长量级递增排列，于是只需要保留result = (n^2)/2
3.如果最高阶项存在且不是1，去掉与这个最高阶相乘的常数得到时间复杂度
除以2相当于是乘以二分之一，去掉它，就得到，result = n^2， 所以这个算法的时间复杂度为O(n^2)。
3.时间复杂度的优劣对比
常见的数量级大小：越小表示算法的执行时间频度越短，则越优；
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)//2的n方<O(n!)<O(nn)//n的n方
网友评论