求的结构是什么,“一定”是把“一”先定下来

“一定”这个词我们再熟悉不过了求的结构是什么。我们从小几乎就学会了说:我们一定要实现什么什么。怎么实现呢?

一定,实际上是一个主谓结构的词,先要把“一”定下来。

不管做什么事情,不管有多少事情要做,都要先梳理清晰,先要把最重要的那件事情确定下来,这就是把“一”定下来。“一”定下来后,这件事情的结构才能形成和展开,能量才能根据结构往相应的层级和方向上去聚集,之后才能逐渐显化成结果。

“一”不确定下来,就是“虚一”。“虚一”便不能产生结构,没有结构,一切所求皆是虚妄。

无论个人还是企业,做决策的时候就是选择“一”的过程。竞争战略之父波特说过,战略就是选择。你选择了这个,就意味着放弃了那个。

当你很确定地选择了一个“一”,就相当于在这个“一”面前停了下来,这叫“止于一”。“止”上面加个“一”,这个字就是“正”。由此,你才能可以做正确的事情和正确地做事。

初识算法——“哎呦,不错哦~”

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

求的结构是什么,“一定”是把“一”先定下来

求的结构是什么,“一定”是把“一”先定下来

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

求的结构是什么,“一定”是把“一”先定下来

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

求的结构是什么,“一定”是把“一”先定下来

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

求的结构是什么,“一定”是把“一”先定下来

求的结构是什么,“一定”是把“一”先定下来

妙不可言——算法复杂性我们首先看一道某公司的招聘试题。

求的结构是什么,“一定”是把“一”先定下来

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

求的结构是什么,“一定”是把“一”先定下来

求的结构是什么,“一定”是把“一”先定下来

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

先看算法1-1:

//算法1-1sum=0;for(i=1;i<=n;i++){sum=sum+pow(-1,i) //pow(-1,i)表示-1的i次幂}这段代码可以实现求和运算,但是为什么不这样算呢?

再看算法1-2:

//算法1-2if(n%2==0) //判断n是不是偶数,%表示求余数 sum=0;else sum=-1;有的人看到这个代码后恍然大悟,原来可以这样啊!这不就是数学家高斯使用的算法吗?

一共50对数,每对之和均为101,那么总和为:(1+100)*50=50501787年,10岁的高斯用了很短的时间算出了结果,而其他孩子却要算很长时间。

可以看出,算法1-1需要运行n+1次,如果n=10000,就要运行10001次,而算法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-3sum=0; //运行1次total=0; //运行1次for(i=1;i<=n;i++) //运行n+1次{ sum=sum+i; //运行n次 for(j=1;j<=n;j++) //运行n*(n+1)次 total=total+i*j; //运行n*n次}把算法的所有语句的运行次数加起来:1+1+n+1+n+n*(n+1)+n*n,可以用一个函数T(n)表达:

当n足够大时,我们可以看到算法运行时间主要取决于第一项,后面的甚至可以忽略不计。

用极限表示为:

,C为不等于0的常数

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

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

还有渐近下界符号 ,如图1-2所示。

从图1-2可以看出,当 时, ,当n足够大时,T(n)和f(n)近似相等,因此,我们用 来表示时间复杂度接近下界。

渐近精确界符号 ,如图1-3所示。

从图1-3中可以看出,当 时, ,当n足够大时,T(n)和f(n)近似相等。这种两边逼近的方式,更加精确近似,因此,用 来表示时间复杂度渐近精确界。

不过,我们通常使用时间复杂度接近上界 来表示时间复杂度。

在算法分析中,渐近复杂度是对算法运行次数的粗略估计,大致反映问题规模增长趋势,而不必精确计算算法的运行时间。

在计算渐近时间复杂度时,可以只考虑对算法运行时间贡献大的语句,而忽略那些运算次数少的语句,循环语句中处在循环内层的语句往往运行次数最多,即为对运行时间贡献最大的语句。例如在算法1-3中,total=total+i*j是对算法贡献最大的语句,只计算该语句的运行次数即可。

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

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

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

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

【空间复杂度】是算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括:

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

上文摘自《趣学算法》,作者陈小玉

更多内容详见《趣学算法》——

趣学算法(异步图书出品)

50 多个实例展示算法的设计、实现、复杂性分析及优化过程培养算法思维感受算法之美

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2895593579@qq.com 举报,一经查实,本站将立刻删除。