上篇算法(1)
算法的渐近增长.png
当 n = 1 时,算法 A 效率不如算法 B(次数比算法 B 要多一次)。而当 n = 2 时,两者效率相同;当 n > 2时,算法 A 就开始优于算法 B 了,随着 n 的增加, 算法 A 比算法 B 越来越好了,得出结论,算法 A 好过 算法 B
二、算法时间复杂度
1、算法时间复杂度定义
2、推导大O阶方法
3、常数阶
高斯算法,时间复杂度不是O(3),而是O(1)。
//第二种算法
int sum = 0, n = 100; /*执行1次*/
sum = (1 + n) * n/2; /*执行1次*/
printf("%d", sum); /*执行1次*/
这个算法的运行次数函数是f(n)=3.根据我们推导大O阶的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本么有最高阶项,所以这个算法的时间复杂度为O(1)。
另外,我们试想一下,如果这个算法当中的语句 sum=(1+n)*n/2有8句,即:
int sum = 0, n = 100; /*执行1次*/
sum = (1 + n) * n/2; /*执行2次*/
sum = (1 + n) * n/2; /*执行3次*/
sum = (1 + n) * n/2; /*执行4次*/
sum = (1 + n) * n/2; /*执行5次*/
sum = (1 + n) * n/2; /*执行6次*/
sum = (1 + n) * n/2; /*执行7次*/
sum = (1 + n) * n/2; /*执行8次*/
printf("%d", sum); /*执行1次*/
事实上无论n为多少,上面的两段代码就是3和10次执行的差异。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之具有O(1)的时间复杂度,又叫常数阶。
注意:不管这个常数是多少,我们都记作O(1),而不能是O(3)、O(10)等其他任何数字,这是初学者常常犯的错误。
对于分支结构而言,无论是真,还是假,执行的次数都是恒定的,不会随着n的变大而发生变化,所以单纯的分支结构(不包含在循环结构中),其时间复杂度也是O(1)。
4、线性阶
// 线性阶
int i;
for (i = 0; i < n; i++) {
/* 时间复杂度为O(1)的程序步骤序列 */
}
```
5、对数阶
>下面的这段代码,时间复杂度又是多少呢?
int count = 1;
while (count < n) {
count = count * 2;
/* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后,就距离n更近了一分。也就是说,有多少个2相乘后大于n,则会退出循环。由2× = n ,得到 x = ㏒2n (2缩小)。所以这个循环的时间复杂度为O(㏒n)。
6、平方阶
下面例子是一个循环嵌套,它的内循环刚才我们已经分析过,时间复杂度为O(n)。
int i, j;
for(i = 0, i < n; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
而对于外层的循环,不过是内部这个时间复杂度为O(n)的语句,再循环n次。所以这段代码的时间复杂度为O(n²)。
如果外循环的循环次数改为了m,时间复杂度就变为O(m x n)。
int i, j;
for(i = 0, i < m; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
所以我们可以总结得出,**循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数**
那么下面这个循环嵌套,它的时间复杂度是多少呢?
int i, j;
for(i = 0, i < m; i++)
{
for (j = i; j < n; j++) /* 注意j = i 而不是 0/
{
/ 时间复杂度为O(1)的程序步骤序列 */
}
}
由于当i=0时,内循环执行了n次,当i = 1时,执行了n-1次,······当i = n-1时,执行了1次,所以总的执行次数为:
n+(n-1)+(n-2)+···+1=n(n+1)/2 = (n²+n)/2
用推导大O阶的方法,第一条,没有加法常数不予考虑;第二条,只保留最高阶项,因此保留n²/2;第三条,去除这个项相乘的常数,也就是取出1/2,最终这段代码的时间复杂度为O(n²)。
从这个例子,我们也可以得到一个经验,其实理解大O推导不算难,难的是对数列的一些相关运算,这更多的是考察数学知识和能力。