数据结构 第2讲 算法复杂性

该内容来源于本人著作《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

如果说数学是皇冠上的一颗明珠,那么算法就是这颗明珠上的光芒,算法让这颗明珠更加熠熠生辉,为科技进步和社会发展照亮了前进的路。数学是美学,算法是艺术。走进算法的人,才能体会它的魅力。

多年来,我有一个梦想,希望每一位提到算法的人,不再立即紧皱眉头,脑海闪现枯燥的公式、冗长的代码;希望每一位阅读和使用算法的人,体会到算法之美,像躺在法国普罗旺斯小镇的长椅上,呷一口红酒,闭上眼睛,体会舌尖上的美味,感受鼻腔中满溢的薰衣草的芳香……

1.1 打开算法之门

瑞士著名的科学家N.Wirth教授曾提出:数据结构+算法=程序。

数据结构是程序的骨架,算法是程序的灵魂。

在我们的生活中,算法无处不在。我们每天早上起来,刷牙、洗脸、吃早餐,都在算着时间,以免上班或上课迟到;去超市购物,在资金有限的情况下,考虑先买什么、后买什么,算算是否超额;在家中做饭,用什么食材、调料,做法、步骤,还要品尝一下咸淡,看看是否做熟。所以,不要说你不懂算法,其实你每天都在用!

但是对计算机专业算法,很多人都有困惑:“I can understand, but I can’tuse!”,我能看懂,但不会用!就像参观莫高窟的壁画,看到它、感受它,却无法走进。我们正需要一把打开算法之门的钥匙,就如陶渊明《桃花源记》中的“初极狭,才通人。复行数十步,豁然开朗。”

1.2 妙不可言——算法复杂性

我们首先看一道某跨国公司的招聘试题。

写一个算法,求下面序列之和:

−1,1,−1,1,…,(−1)n

当你看到这个题目时,你会怎么想?for语句?while循环?

先看算法1-1:

//算法1-1 
sum=0;
for(i=1; i<=n; i++)
{
  sum=sum+(-1)^n;
}

这段代码可以实现求和运算,但是为什么不这样算?!

再看算法1-2:

//算法1-2
if(n%2==0)  //判断n是不是偶数,%表示求余数
  sum =0;
else
  sum=-1;

有的人看到这个代码后恍然大悟,原来可以这样啊?这不就是数学家高斯使用的算法吗?

一共50对数,每对之和均为101,那么总和为:

(1+100)×50=5050

1787年,10岁的高斯用了很短的时间算出了结果,而其他孩子却要算很长时间。

可以看出,算法1-1需要运行n+1次,如果n=100 00,就要运行100 01次,而算法1-2仅仅需要运行1次!是不是有很大差别?

高斯的方法我也知道,但遇到类似的题还是……我用的笨办法也是算法吗?

答:是算法。

算法是指对特定问题求解步骤的一种描述。

算法只是对问题求解方法的一种描述,它不依赖于任何一种语言,既可以用自然语言、程序设计语言(C、C++、Java、Python等)描述,也可以用流程图、框图来表示。一般为了更清楚地说明算法的本质,我们去除了计算机语言的语法规则和细节,采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间,它更符合人们的表达方式,容易理解,但不是严格的程序设计语言,如果要上机调试,需要转换成标准的计算机程序设计语言才能运行。

算法具有以下特性。

(1)有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。

(2)确定性:每条语句有确定的含义,无歧义。

(3)可行性:算法在当前环境条件下可以通过有限次运算实现。

(4)输入输出:有零个或多个输入,一个或多个输出。

算法1-2的确算得挺快的,但如何知道我写的算法好不好呢?

“好”算法的标准如下。

(1)正确性:正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期的需求。

(2)易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。

(3)健壮性:算法对非法数据及操作有较好的反应和处理。例如,在学生信息管理系统中登记学生年龄时,若将21岁误输入为210岁,系统应该提示出错。

(4)高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次,因此不能用秒来具体计算算法消耗的时间,由于相同配置的计算机进行一次基本运算的时间是一定的,我们可以用算法基本运算的执行次数来衡量算法的效率。因此,将算法基本运算的执行次数作为时间复杂度的衡量标准。

(5)低存储性:低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备,算法如果占用空间过大,则无法运行。算法占用的空间大小称为空间复杂度。

除了(1)~(3)中的基本标准外,我们对好的算法的评判标准就是高效率、低存储。

(1)~(3)中的标准都好办,但时间复杂度怎么算呢?

时间复杂度:算法运行需要的时间,一般将算法的执行次数作为时间复杂度的度量标准。

看算法1-3,并分析算法的时间复杂度。

//算法1-3 
sum=0;                     //运行1次
total=0;                   //运行1次
for(i=1; i<=n; i++)        //运行n次
{
  sum=sum+i;               //运行n次
  for(j=1; j<=n; j++)      //运行n*n次
    total=total+i*j;       //运行n*n次
}

把算法的所有语句的运行次数加起来:1+1+n+n+n×n+n×n,可以用一个函数T(n)表达:

T(n)=2n2+2n+2

当n足够大时,例如n=105时,T(n)=2×1010+2×105+2,我们可以看到算法运行时间主要取决于第一项,后面的甚至可以忽略不计。

用极限表示为:

,C为不等于0的常数

如果用时间复杂度的渐近上界表示,如图1-1所示。

从图1-1中可以看出,当n

n0时,T(n)

Cf (n),当n足够大时,T(n)和f (n)近似相等。因此,我们用О(f (n))来表示时间复杂度渐近上界,通常用这种表示法衡量算法时间复杂度。算法1-3的时间复杂度渐近上界为О(f (n))=О(n2),用极限表示为:

图1-1 渐近时间复杂度上界

还有渐近下界符号Ω(T(n)

Cf (n)),如图1-2所示。

图1-2 渐近时间复杂度下界

从图1-2可以看出,当n

n0时,T(n)

Cf (n),当n足够大时,T(n)和f (n)近似相等,因此,我们用Ω(f (n))来表示时间复杂度渐近下界。

渐近精确界符号Θ(C1f (n)

T(n)

C2f (n)),如图1-3所示。

从图1-3中可以看出,当n

n0时,C1f (n)

T(n)

C2f (n),当n足够大时,T(n)和f (n)近似相等。这种两边逼近的方式,更加精确近似,因此,用Θ (f (n))来表示时间复杂度渐近精确界。

图1-3 渐进时间复杂度精确界

我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。

看算法1-4,并分析算法的时间复杂度。

//算法1-4
i=1;              //运行1次
while(i<=n)     //可假设运行x次
{
  i=i*2;         //可假设运行x次
}

观察算法1-4,无法立即确定while 及i=i*2运行了多少次。这时可假设运行了x次,每次运算后i值为2,22,23,…,2x,当i=n时结束,即2x=n时结束,则x=log2n,那么算法1-4的运算次数为1+2log2n,时间复杂度渐近上界为О(f (n))=О(log2n)。

在算法分析中,渐近复杂度是对算法运行次数的粗略估计,大致反映问题规模增长趋势,而不必精确计算算法的运行时间。在计算渐近时间复杂度时,可以只考虑对算法运行时间贡献大的语句,而忽略那些运算次数少的语句,循环语句中处在循环内层的语句往往运行次数最多,即为对运行时间贡献最大的语句。例如在算法1-3中,total=total+i*j是对算法贡献最大的语句,只计算该语句的运行次数即可。

注意:不是每个算法都能直接计算运行次数。

例如算法1-5,在a[n]数组中顺序查找x,返回其下标i,如果没找到,则返回−1。

//算法1-5 
findx(int x)      //在a[n]数组中顺序查找x
{ 
for(i=0; i<n; i++)  
{
   if (a[i]==x)  
     return i;    //返回其下标i
   }
  return -1;
}

我们很难计算算法1-5中的程序到底执行了多少次,因为运行次数依赖于x在数组中的位置,如果第一个元素就是x,则执行1次(最好情况);如果最后一个元素是x,则执行n次(最坏情况);如果分布概率均等,则平均执行次数为(n+1)/2。

有些算法,如排序、查找、插入等算法,可以分为最好、最坏和平均情况分别求算法渐近复杂度,但我们考查一个算法通常考查最坏的情况,而不是考查最好的情况,最坏情况对衡量算法的好坏具有实际的意义。

我明白了,那空间复杂度应该就是算法占了多大存储空间了?

空间复杂度:算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。

空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括:

(1)输入/输出数据;

(2)算法本身;

(3)额外需要的辅助空间。

输入/输出数据占用的空间是必需的,算法本身占用的空间可以通过精简算法来缩减,但这个压缩的量是很小的,可以忽略不计。而在运行时使用的辅助变量所占用的空间,即辅助空间是衡量空间复杂度的关键因素。

看算法1-6,将两个数交换,并分析其空间复杂度。

//算法1-6 
swap(int x,int y)  //x与y交换 
{ 
  int temp;
  temp=x;  //temp为辅助空间 ①
  x=y;   ②
  y=temp; ③
}

两数的交换过程如图1-4所示。

图1-4 两数交换过程

图1-4中的步骤标号与算法1-6中的语句标号一一对应,该算法使用了一个辅助空间temp,空间复杂度为О(1)。

注意:递归算法中,每一次递推需要一个栈空间来保存调用记录,因此,空间复杂度需要计算递归栈的辅助空间。

看算法1-7,计算n的阶乘,并分析其空间复杂度。

//算法1-7 
fac(int n)  //计算n的阶乘
{  
  if(n<0)   //小于零的数无阶乘值
  {  
     printf("n<0,data error!"); 
     return -1;
  }
  else if(n= =0 || n= =1) 
           return 1; 
         else 
           return n*fac(n-1); 
}

阶乘是典型的递归调用问题,递归包括递推和回归。递推是将原问题不断分解成子问题,直到达到结束条件,返回最近子问题的解;然后逆向逐一回归,最终到达递推开始的原问题,返回原问题的解。

思考:试求5的阶乘,程序将怎样计算呢?

5的阶乘的递推和回归过程如图1-5和图1-6所示。

图1-5 5的阶乘递推过程

图1-6 5的阶乘回归过程

图1-5和图1-6的递推、回归过程是我们从逻辑思维上推理,用图的方式形象地表达出来的,但计算机内部是怎样处理的呢?计算机使用一种称为“栈”的数据结构,它类似于一个放一摞盘子的容器,每次从顶端放进去一个,拿出来的时候只能从顶端拿一个,不允许从中间插入或抽取,因此称为“后进先出”(last in first out)。

5的阶乘进栈过程如图1-7所示。

图1-7 5的阶乘进栈过程

5的阶乘出栈过程如图1-8所示。

图1-8 5的阶乘出栈过程

从图1-7和图1-8的进栈、出栈过程中,我们可以很清晰地看到,首先把子问题一步步地压进栈,直到得到返回值,再一步步地出栈,最终得到递归结果。在运算过程中,使用了n个栈空间作为辅助空间,因此阶乘递归算法的空间复杂度为О(n)。在算法1-7中,时间复杂度也为О(n),因为n的阶乘仅比n−1的阶乘多了一次乘法运算,fac(n)=n*fac(n−1)。如果用T(n)表示fac(n)的时间复杂度,可表示为:

T(n)= T(n−1)+1

                  = T(n−2)+1+1

                  ……

                  = T(1)+…+1+1

                  =n

1.3 美不胜收——魔鬼序列

趣味故事1-1:一棋盘的麦子

有一个古老的传说,有一位国王的女儿不幸落水,水中有很多鳄鱼,国王情急之下下令:“谁能把公主救上来,就把女儿嫁给他。”很多人纷纷退让,一个勇敢的小伙子挺身而出,冒着生命危险把公主救了上来,国王一看是个穷小子,想要反悔,说:“除了女儿,你要什么都可以。”小伙子说:“好吧,我只要一棋盘的麦子。您在第1个格子里放1粒麦子,在第2个格子里放2粒,在第3个格子里放4粒,在第4个格子里放8粒,以此类推,每一格子里的麦子粒数都是前一格的两倍。把这64个格子都放好了就行,我就要这么多。”国王听后哈哈大笑,觉得小伙子的要求很容易满足,满口答应。结果发现,把全国的麦子都拿来,也填不完这64格……国王无奈,只好把女儿嫁给了这个小伙子。

解析

棋盘上的64个格子究竟要放多少粒麦子?

把每一个放的麦子数加起来,总和为S,则:

S=1+21+22+23+…+263   ①

我们把式①等号两边都乘以2,等式仍然成立:

2S=21+22+23+…+263+264   ②

式 ②减去式①,则:

S=264−1 =18 446 744 073 709 551 615

据专家统计,每个麦粒的平均重量约41.9毫克,那么这些麦粒的总重量是:

   18 446 744 073 709 551 615×41.9=772 918 576 688 430 212 668.5(毫克)

                   ≈7729(亿吨)

全世界人口按60亿计算,每人可以分得128吨!

我们称这样的函数为爆炸增量函数,想一想,如果算法时间复杂度是О(2n) 会怎样?随着n的增长,这个算法会不会“爆掉”?经常见到有些算法调试没问题,运行一段也没问题,但关键的时候宕机(shutdown)。例如,在线考试系统,50个人考试没问题,100人考试也没问题,如果全校1万人考试就可能出现宕机。

注意:宕机就是死机,指电脑不能正常工作了,包括一切原因导致的死机。计算机主机出现意外故障而死机,一些服务器(如数据库)死锁,服务器的某些服务停止运行都可以称为宕机。

常见的算法时间复杂度有以下几类。

(1)常数阶。

常数阶算法运行的次数是一个常数,如5、20、100。常数阶算法时间复杂度通常用О(1)表示,例如算法1-6,它的运行次数为4,就是常数阶,用О(1)表示。

(2)多项式阶。

很多算法时间复杂度是多项式,通常用О(n)、О(n2)、О(n3)等表示。例如算法1-3就是多项式阶。

(3)指数阶。

指数阶时间复杂度运行效率极差,程序员往往像躲“恶魔”一样避开它。常见的有О(2n)、О(n!)、О(nn)等。使用这样的算法要慎重,例如趣味故事1-1。

(4)对数阶。

对数阶时间复杂度运行效率较高,常见的有О(logn)、О(nlogn)等,例如算法1-4。

常见时间复杂度函数曲线如图1-9所示。

图1-9 常见函数增量曲线

从图1-9中可以看出,指数阶增量随着x的增加而急剧增加,而对数阶增加缓慢。它们之间的关系为:

О(1)< О(logn)< О(n)< О(nlogn) < О(n2)< О(n3)< О(2n) < О(n!)< О(nn)

我们在设计算法时要注意算法复杂度增量的问题,尽量避免爆炸级增量。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏肖力涛的专栏

NLP 点滴 :文本相似度 (上)

在自然语言处理过程中,经常会涉及到如何度量两个文本之间的相似性,我们都知道文本是一种高维的语义空间,如何对其进行抽象分解,从而能够站在数学角度去量化其相似性。

2.2K10
来自专栏Aloys的开发之路

C语言中随机数相关问题

用C语言产生随机数重要用到rand函数、srand函数、及宏RAND_MAX(32767),它们均在stdlib.h中进行了声明。 int rand(void)...

75480
来自专栏Python数据科学

机器学习“特征编码”的经验分享:鱼还是熊掌?

我们拿到的数据通常比较脏乱,可能会带有各种非数字特殊符号,比如中文。下面这个表中显示了我们最原始的数据集。而实际上机器学习模型需要的数据是数字型的,因为只有数字...

42110
来自专栏程序员宝库

码农也要学算法

当“人工智能”、“AlphaGo”、“无人驾驶”、“智能投顾”等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算机通过提供给人类每天要面临的...

501100
来自专栏C/C++基础

网易游戏技术岗在线编程题(一)

小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2...

8810
来自专栏落影的专栏

程序员进阶之算法练习(二十四)

前言 已经有三个月未更新算法文章,大厂工作环境是步步紧逼的,使得所有的人越来越忙碌。余下的学习时间,要用于技术预研、知识面开阔、底层原理理解等等,慢慢算法只能占...

41770
来自专栏机器学习算法与Python学习

Encoder-Decoder自动生成对联,要试试么?

另外,点击阅读原文尝试微软的自动对联系统(http://duilian.msra.cn/app/couplet.aspx)

13400
来自专栏数据派THU

手把手教你由TensorFlow上手PyTorch(附代码)

来源:机器之心 作者:Illarion Khlestov 本文为你解读PyTorch 的易用性。 当我第一次尝试学习 PyTorch 时,没几天就放弃了。和 ...

98140
来自专栏互联网大杂烩

机器学习面试

线性回归的因变量是连续变量,自变量可以是连续变量,也可以是分类变量。如果只有一个自变量,且只有两类,那这个回归就等同于t检验。如果只有一个自变量,且有三类或更多...

11240
来自专栏机器之心

教程 | 如何从TensorFlow转入PyTorch

选自Medium 作者:Illarion Khlestov 机器之心编译 参与:李泽南、黄小天 当我第一次尝试学习 PyTorch 时,没几天就放弃了。和 Te...

743150

扫码关注云+社区

领取腾讯云代金券