算法
算法的定义多种多样,一般算法被认为是解决问题的途径,这种可以看做从算法的目的上理解。如果从算法的过程理解,计算机算法可以看做有限操作的集合。
算法的效率
算法效率的评估标准:
- 时间复杂度:评估执行程序所需要的时间。可以估算出程序对处理器的使用程度。
- 空间复杂度:评估执行程序所需要的存储空间。可以估算出程序对内存的使用程度。
空间复杂度的分析比时间复杂度更为简单,所以设计算法时候,时间复杂度比空间复杂度更容易出现问题,这里着重说明时间复杂度。
时间复杂度
时间频度:一个算法中语句的执行次数,通常用T(n)表示,n为问题规模。
时间复杂度:假设有这样一个函数f(n),当n趋于无穷大的时候,T(n)/f(n)的极限值是一个非0常数,那么f(n)可以称作T(n)的同数量级函数,记作T(n)=O(f(n))。也就是算法的时间增长率和f(n)的增长率正相关,也就是算法的渐近时间复杂度,简称时间复杂度。
常见的时间复杂度有:
- 常数阶 O(1)
- 对数阶 O(log$n$)
- 线性阶 O(1)
- 线性对数阶 O($n$log$n$)
- 平方阶 O($n^2$)
- 立方阶 O($n^3$)
- k次方阶 O($n^k$)
推导O(f(n))的规则:
- 用常数1取代运行次数的所有加法常数;
- 只保留最高阶;
- 去掉最高阶的常数。
常数阶
1 | let sum = 0, n = 10; // 代码执行1次 |
代码执行3次,所以时间复杂度O(1)。
对数阶
1 | let num = 1; // 执行1次 |
这段代码执行的边界就执行到number大于等于2,假设m为循环体执行次数,则$2^m$ = n,那么m=log$n$。所以语句执行2log$n$+1,时间复杂度为O(log$n$)。
线性阶
1 | let i = 0; // 执行1次 |
代码执行3n+1次,所以时间复杂度为O(n)。
平方阶
1 | for(let i = 0;i < n;i++){ // 执行n次 |
代码执行2$n^2$+n,所以时间复杂度为O($n^2$)。
常见时间复杂度比较
O(1) < O(log$n$) < O(n) < O(nlog$n$) < O($n^2$) < O($2^n$) < O(n!)
简明的理解就是,随着问题规模n不断增大,上述时间复杂度也不断增大,并且O($2^n$)和O(n!)的增长率(增长的快慢)会远远大于O(1) ,O(log$n$), O(n) 和 O(nlog$n$) 的增长率,所以O($2^n$)和O(n!)属于复杂度较高的算法,这几种算法的效率极差,应该避免出现在程序中。