什么是算法?
算法解决某个特定问题步骤的描述。
算法的特性
- 输入:可以是零个或者多个输入。
- 输出:可以是一个或者多个输出。
- 有穷性:无限循环肯定是不可以的。
- 确定性:相同的输入,一定要得到相同的输出。
- 可行性:每一步都必须在有限次数内完成。
算法的设计要求
- 正确性:可以正确的解决问题
- 可读性:方便阅读、理解和交流
- 健壮性:输入不合法会做出相应的处理。
- 效率高且存储量低。
算法效率的度量方法
算法的效率一般是指执行的时间。
事后统计法
对比多种算法的执行时间。
事前估算法
假如我们要求解1+2+3+···+100
的和:
算法1:
sum,n := 0,100 // 执行1次
for i:=1; i<=n; i++ { // 执行 n+1 次
sum +=i // 执行 n 次
}
算法2:
sum, n := 0,100 // 执行 1 次
sum = n*(n+1)/2 // 执行 1 次
很显然算法一执行了2n+2
次,算法二执行了2 次。忽略掉算法的第一行指令,也就是n次与1次的差别。
假设有一个算法3是下面的内容:
sum,n,m := 0,100,200
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
sum ++ // 执行了 n * n 次
}
}
我们通常在估算算法的效率时通常会忽略常数项,只是比较最高次幂。
比如说:算法A是 2n*n
,算法B是 3n+1
,算法C 是 2n*n+3n+1
。那么算法A的时间复杂度是O(n*n),算法B的时间复杂度是O(n),算法C的时间复杂度是O( n * n )
算法的时间复杂度
我们通常用O来表示算法的时间复杂度。
O(1) 通常称为:常数阶
O(n)通常称为:线性阶
O(n*n)通常称为:平方阶
我们通过例子来学习推导:
常数阶
sum, n := 0,100 // 执行 1 次
sum = n*(n+1)/2 // 执行 1 次
上面的代码执行了2次,但是我们通常会忽略常数项,把这段代码的时间复杂度计为O(1)
。也就是我们说的常数阶,哪怕这段代码执行了10次,也是计为O(1)
线性阶
sum,n := 0,100 // 执行1次
for i:=1; i<=n; i++ { // 执行 n+1 次
sum +=i // 执行 n 次
}
在计算时间复杂度的时候,我们通常是忽略掉常数,并将最高次幂的常数项设为1,所以上述代码的时间复杂度为:O(n)
。通常称为常数阶。
对数阶
count, n :=1, 100
for {
if count > n {
break
}
count = count * 2
}
由于每次count
乘以 2 之后就距离 n 更近一步了。2^x = n
所以 x = logn
时间复杂度也就是为O(logn)
平方阶
sum,n,m := 0,100,200
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
sum ++ // 执行了 n * n 次
}
}
这段代码的时间复杂度为: O(n^2)
循环的时间复杂度等于循环体的复杂度乘以循环的次数。
时间复杂度消耗时间的顺序:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
网友评论