我们知道学习数据结构与算法主要是解决一个「快」和「省」的问题, 如何让代码执行更快, 如何更节省空间. 那么如何来考量你的代码的执行效率呢, 我们总要有一个标准, 这就是我今天所讲的复杂度分析, 不夸张的说, 掌握好复杂度分析, 数据结构与算法你就掌握了一半, 所有的算法都逃不出复杂度分析的范畴.
复杂度分析包括时间复杂度和空间复杂度.
如何考量我们代码的执行效率, 有的人可能会说我在计算机上跑一下不得了, 简单便捷, 没错, 这样确实可以. 但是这种方法太依赖硬件环境了, 你在不同的机器上跑的时间肯定是不一样的. 所以, 我们需要一种不依靠测试环境, 不需要测试数据的方法来估计算法的执行效率的方法. 大 O 时间复杂度上场了.
大 O 复杂度表示法
直接上代码, 我会带你一起来估算代码的运行时间, 在实战中掌握大 O 复杂度.
- int sum(int n)
- {
- int sum = 0;
- int i = 1;
- for(; i<=n; i++)
- {
- sum = sum + i;
- }
- return sum;
- }
上面是一个计算从 1 + 2 + 3 + ... + n 的求和, 我们假设每行代码的执行时间都是一个 unit_time. 我们可以看到第 3,4 行的代码都运行了 1 个 unit_time, 第 6,8 行都运行了 n 个 unit_time. 所以这段代码运行时间为 T(n) = (2n+2) * unit_time. 即 T(n) = O(2n+2), 这就是大 O 时间复杂度表示法. 当 n 趋向于无穷大时, 记为 T(n) = O(n).
大 O 时间复杂度表示法实际上并不表示代码真正的执行时间, 大家也看到了, T(n) 才是代码真正的执行时间, 大 O 时间复杂度是表示代码执行时间随数据规模增长的变化趋势.
算法的时间复杂度采用这种数量级的形式表示后, 将给分析算法的时间复杂度带来很大的方便. 即对一个算法, 只需分析影响该算法时间复杂度的主要部分即可, 而无需对该算法的每一个语句都进行纤细的分析.
时间复杂度分析
那么问题来了, 给我们一段代码, 我们怎么分析它的时间复杂度呢? 我有二个实操的方法可以分享给你.
1. 关注执行次数最多的一段代码
在上面那个例子中, 执行次数最多的是第 6,8 行, 所以总的时间复杂度就是 O(n).
2. 关注量级最大的那段代码
看下面代码, 你可以先试着分析一下, 再往下翻.
- int sum(int n)
- {
- int sum_1 = 0;
- int x = 1;
- for(; p< 10; p++) {
- sum_1 += p;
- }
- int sum_2 = 0;
- int q = 1;
- for(; q< n; q++) {
- sum_2 += q;
- }
- int sum_3 = 0;
- int i = 1;
- for(; i<=n; i++) {
- int j = 1;
- for(; j<=n; j++) {
- sum_3 = sum_3 + i *j;
- }
- }
- return sum_1 + sum_2+ sum_3;
- }
第一段执行了 10 次, 这是一个常量的执行时间, 跟 n 的规模无关, 就算它执行一百次, 一千次, 它也是常量级的执行时间. 所以为 O(1).
第二段和第三段代码分别为 O(n),O(n2), 这对你应该不是很难. 所以我们只关注量级最大的代码的时间复杂度, 即 O(n2).
大 O 表示法有乘法法则和加法法则, 非常好理解, 乘法法则实际上就是嵌套循环. 相信你已经懂了时间复杂度的大 O 分析法了.
下面我介绍一些常见的时间复杂度分析实例.
- (敲黑板, 划重点了, 拿小本本记下)
- 1. O(1)
O(1) 常量级时间复杂度
- int x = 1;
- int y = 2;
- int sum = x + y;
- 1. O(logn)
- i = 1;
- while( i <= n)
- {
- i = i * 2;
- }
代码的执行次数为 x = log2n, 即求解方程 2x = n.
复杂度分析并不难, 关键在于多练 (感觉). 只要跟着我的思路学习, 练习, 很快, 你看到代码, 简单的你能一眼看出复杂度, 难的你也不会畏惧, 分析一下就出来了.
给我个喜欢 ( ω ), 欢迎关注我哦!
来源: http://www.jianshu.com/p/98bce5cf53aa