算法复杂度分析(1)
为什么需要算法复杂度分析,实际运行一遍然后收集运行的信息和统计不就可以了?这总事后分析的方法确实没有错,但是当环境发生变化,数据量发生变化,或者数据模型改变了,程序的执行效率就有可能发生巨大的改变,所以我们需要一种粗略的,不需要具体测试数据的估算程序执行效率的方法,而这种方法就是复杂度分析。
大 O 复杂度表示法
大 O 表示法是一种特殊的表示法,指出了算法的速度有多快或者多慢。谁在乎呢?实际上,你经常要使用别人编写的算法,在这种情况下,知道这些算法的速度大有裨益。
这里我们拿一段代码来进行解释:
_7int fun(int n) {_7 int num = 0;_7 for (int i = 1; i <= n; i++) {_7 sum = sum + i;_7 }_7 return sum;_7}
这段代码是用来求数列和的,我们把每一句代码执行的时间记为 1u,然后默认每句基础代码执行的时间都是一样的,从上面的代码我们可以看出,int num = 0;
和int i = 1;
各执行了 1 次,sum = sum + i;
和i++
各执行了 n 次,return
部分我们不看,那么这个函数所执行的总时间就应该是(2n+2)*1u
,我们把总时间记为 T(n)那么,可以看出执行的总时间和 n 成正比关系,即和执行次数成正比关系,而这种规律我们可以总结成一个公式即:
T(n) = O[f(n)]
而上一个公式就可以表示成T(n) = O(2n+2)
,当 n 到大一定程度的时候我们就可以把+2 和 n 的系数 2 给忽略掉,这时候的T(n) = O(n)
,这就是我们常说的 O(n)时间复杂度或 O(n)空间复杂度的由来。
时间复杂度分析
那么当代码越来越长,越来越庞大是时候难道还这样一步步分析吗?当然不是,当我们对算法或者程序进行分析的时候我们只需要关注以下几点即可:
1. 只关注循环次数最多的代码
还是拿上面一段代码来分析。
_7int fun(int n) {_7 int num = 0;_7 for (int i = 1; i <= n; i++) {_7 sum = sum + i;_7 }_7 return sum;_7}
从代码中我们可以看出,只有一个循环 n 次的 for 循环,而其他部分的代码只执行了一次,这时我们就可以直接忽略掉那些只执行一次的代码,只关注执行最多的代码,即 for 循环中的代码,所以这个函数的时间复杂度就是 O(n)。
2. 加法法则:只关注执行次数最多的代码的时间复杂度
_14int fun(int n) {_14 for (int i = 0; i < 10; i++) {_14 System.out.println("a");_14 }_14 for (int i = 0; i < n; i++) {_14 System.out.println("a");_14 }_14 for (int i = 0; i < n*10; i++) {_14 System.out.println("a");_14 }_14 for (int i = 0; i < n*n; i++) {_14 System.out.println("a");_14 }_14}
从上面的代码我们可以看到 4 个 for 循环这时候应该如何判断呢?首先我们先找出它们各自循环了几次,第一个执行了 10 次,第二个执行了 n 次,第三个执行了 10n 次,第四个执行了 n2 次,这时候我们只需要关注执行最多的那个循环的复杂度即可,即第四次(我们均默认 n 很大),所以这段函数的时间复杂度为 O(n2)。
3. 乘法法则:嵌套代码的时间复杂度等于嵌套内外的时间复杂度的乘积
_11int fun(int n) {_11 for (int i = 0; i < n; i++) {_11 cal(n);_11 }_11}_11_11int cal(int n) {_11 for (int i = 0; i < n; i++) {_11 System.out.println("a");_11 }_11}
从上方代码看出,fun 函数中的 for 循环每次循环都需要调用一次 cal 函数,而我们可以很轻松的判断出 cal 函数的时间复杂度是 O(n),而 fun 一共需要调用 n 次 cal 函数,即 O(n) * O(n),即 O(n*n),简化下就是 O(n2)。
到这里我们就基本讲完了时间复杂度的分析方法了,下面我们就来看以下几种常见 的算法时间复杂度。