【算法专栏】-- 谈谈时间复杂度

栏目: 编程工具 · 发布时间: 5年前

内容简介:虽然随着计算机硬件的迭代更新,运算处理的性能越来越强,但实际上,它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序,我们就需要考虑到衡量算法的

不管是 Android 代码还是数据结构的设计,都涉及到算法的问题,其中时间复杂度是一个Core,这篇文章我们就一起聊聊时间复杂度的原理!

1、算法效率

虽然随着计算机硬件的迭代更新,运算处理的性能越来越强,但实际上,它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序,我们就需要考虑到 “算法的效率”

衡量算法的 “好坏”“效率” 主要由以下两个指标(复杂度)来评估:

:sparkles: 时间复杂度(运行时间): 评估执行程序所需的时间,可以估算出程序对处理器的使用程度。 (本篇博文我们重点探讨时间复杂度)

:sparkles:  空间复杂度(占用空间): 评估执行程序所需的存储空间,可以估算出程序对计算机内存的使用程度。

2、算法事例

我们通过几个场景引出时间复杂度的概念,以及常见的几种时间复杂度,最后再总结比较它们的优劣!

场景一

生活场景: 你买了一箱“牛栏山二锅头”(16瓶),2天喝一瓶,全部喝完需要几天?

很简单的算术问题,2 ✖ 16 = 32 天,那如果一箱有 n 瓶,则需要 2 ✖ n = 2n 天,如果我们用一个函数来表达这个相对时间,可以记作 T(n) = 2n

代码场景:

for(int i = 0; i < n; i++){               // 执行次数是线性的
        System.out.println("喝一瓶酒");
        System.out.println("等待一天");
    }

场景二

生活场景: 你又买了一箱“牛栏山二锅头”(16瓶),决定换个法子喝,5天为一个周期,喝剩下酒的一半,于是第一次喝 8 瓶,第二次喝 4 瓶,那么喝到最后一瓶需要几天?

这个问题其实也很简单,16/2 = 8,8/2 = 4,4/2 = 2,2/2 = 1(还剩一瓶),这不就是对数函数吗?以 2 为底数,16为真数,得到的对数就是我们需要的答案!我们可以简写为:5log16,如果一箱有 n 瓶,则需要 5logn 天,如果我们用一个函数来表达这个相对时间,可以记作 T(n) = 5logn

代码场景:

for(int i = 1; i < n; i *= 2){
       System.out.println("喝一瓶酒");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");

场景三

生活场景: 酒喝多了,买了一瓶枸杞,3天喝一瓶,请问喝完枸杞要几天?

是的,你没听错,我只是问你喝完枸杞要多久?答案很简单:3天!如果我们用一个函数来表达这个相对时间,可以记作: T(n) = 3

代码场景:

void drink(int n){
   System.out.println("喝一瓶枸杞");
   System.out.println("等待一天");
   System.out.println("等待一天");

场景四

生活场景: 酒瘾难戒,又买了一箱好酒(6瓶),但是又不能多喝,于是第一瓶喝了1天,第二瓶喝了2天,第三瓶喝了3天,这样下去全部喝完需要几天?

不用我说,其实这就是一个 1 + 2 + 3 ... + 6 的算术问题,我们知道有个公式:6(6+1)/2 = 21 天,那如果有 n 瓶,就需要 n(n+1)/2 天,如果我们用一个函数来表达这个相对时间,可以记作 T(n) = n²/2 + n/2

代码场景:

void drink(int n){
   for(int i = 0; i < n; i++){
       for(int j = 0; j < i; j++){
           System.out.println("等待一天");
       }
       System.out.println("喝一瓶酒");
   }
}

3、渐进时间复杂度

有了基本操作执行次数的函数 T(n),是否就可以分析和比较一段代码的运行时间了呢?还是有一定的困难。比如算法 A 的相对时间是 T(n) = 100n ,算法 B 的相对时间是 T(n) = 5n² ,这两个到底谁的运行时间更长一些? 这就要看 n 的取值了!

所以,这时候有了 “渐进时间复杂度” (asymptotic time complectiy)的概念。

我们看看官方的定义:

若存在函数 f(n),使得当 n 趋近于无穷大时,T(n) / f(n) 的极限值为不等于零的常数,则称 f(n) 是 T(n) 的同数量级函数。记作 T(n)= O(f(n)),称 O(f(n)) 为算法的 “渐进时间复杂度” ,简称 “时间复杂度” 。渐进时间复杂度用大写 O 来表示,所以也被称为 “大O表示法”

4、推导原则

如何推导出时间复杂度呢?有如下几个原则:

:sparkles: 1、如果运行时间是常数量级,用常数 1 表示;

:sparkles: 2、只保留时间函数中的最高阶项;

:sparkles: 3、如果最高阶项存在,则省去最高阶项前面的系数。

5、事例再分析

场景一

相对时间: T(n) = 2n ,根据推导原则三:最高阶数为 2n ,省去系数 2 ,转换后的时间复杂度为: T(n) = O(n)

场景二

相对时间: T(n) = 5logn ,根据推导原则三:最高阶数为 5logn ,省去系数 5 ,转换后的时间复杂度为: T(n) = O(logn)

场景三

相对时间: T(n) = 3 ,根据推导原则一:只有常数量级 ,用常数 1 表示 ,转换后的时间复杂度为: T(n) = O(1)

场景四

相对时间: T(n) = n²/2 + n/2 ,根据推导原则二:最高阶数为 n²/2 ,省去系数 0.5 ,转换后的时间复杂度为: T(n) = O(n²)

这四种时间复杂度究竟谁用时更长,谁节省时间呢? O(1) < O(logn) < O(n) < O(n²)

6、其他常见复杂度

除了常数阶、线性阶、平方阶、对数阶,还有如下时间复杂度:

f(n) 时间复杂度
nlogn O(nlogn) nlogn 阶
O(n³) 立方阶
2ⁿ O(2ⁿ) 指数阶
n! O(n!) 阶乘阶
(√n) O(√n) 平方根阶

7、复杂度比较

n logn √n nlogn 2ⁿ n!
5 2 2 10 25 32 120
10 3 3 30 100 1024 3628800
50 5 7 250 2500 约10^15 约3.0*10^64
100 6 10 600 10000 约10^30 约9.3*10^157
1000 9 31 9000 1000 000 约10^300 约4.0*10^2567

从上表可以看出,O(n)、O(logn)、O(√n)、O(nlogn) 随着 n 的增加,复杂度提升不大,因此这些复杂度属于效率比较高的算法,反观 O(2ⁿ) 和 O(n!) 当 n 增加到 50 时,复杂度就突破十位数了,这种效率极差的复杂度最好不要出现在程序中,因此在动手编程时要评估所写算法的最坏情况的复杂度。

这些时间复杂度究竟谁用时更长,谁节省时间呢?

O(1) < O(logn) < O(√n) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

8、再举一例

:confused:【疑问】:confused::现在计算机硬件性能越来越强,算法真的体验那么明显吗?算法时间复杂度真的需要那么重视吗?

我相信你肯定存在这样的疑问,虽然我们知道算法这个东西是很重要的,但是我们平常可能接触不多,很多时候计算机的性能已经能满足我们的需求,但是我还是要举个例子让你更直观的看到不同算法之间的巨大差异!

:boom: 算法 A 的相对时间规模是 T(n) = 100n,时间复杂度是 O(n),算法 A 运行在老旧电脑上。

:boom: 算法 B 的相对时间规模是 T(n) = 5n²,时间复杂度是 O(n²),算法 B 运行在某台超级计算机上,运行速度是老旧电脑的 100 倍。

当随着 n 的增大,我们通过表格看看 T(n) 的变化:

n T(n) = 100n ✖ 100 T(n) = 5n²
1 10000 5
5 50000 125
10 10 0000 500
100 100 0000 50000
1000 1000 0000 500 0000
2000 2000 0000 2000 0000
10000 1 0000 0000 5 0000 0000
100000 10 0000 0000 500 0000 0000
1000000 100 0000 0000 50000 0000 0000

从表格中可以看出,当 n 的值很小的时候,算法 A 的运行用时要远大于算法 B;当 n 的值达到 1000 左右,算法 A 和算法 B 的运行时间已经接近;当 n 的值达到 2000 左右,算法 A 和 算法 B 的运行时间一致;当 n 的值越来越大,达到十万、百万时,算法 A 的优势开始显现,算法 B 则越来越慢,差距越来越明显。这就是不同时间复杂度带来的差距,即便你的计算机很牛X!

参考博客

一套图 搞懂“时间复杂度”


以上所述就是小编给大家介绍的《【算法专栏】-- 谈谈时间复杂度》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C++程序设计

C++程序设计

谭浩强 / 清华大学出版社 / 2004-6-1 / 36.00元

《C++程序设计》作者深入调查了我国大学的程序设计课程的现状和发展趋势,参阅了国内外数十种有关C++的教材,认真分析了学习者在学习过程中遇到的困难,研究了初学者的认识规律。在本书中做到准确定位,合理取舍内容,设计了读者易于学习的教材体系,并且以通俗易懂的语言化解了许多复杂的概念,大大减少了初学者学习C++的困难。C++是近年来国内外广泛使用的现代计算机语言,它既支持面向过程的程序设计,也支持基于对......一起来看看 《C++程序设计》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

在线进制转换器
在线进制转换器

各进制数互转换器

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具