算法介绍从一个简单加法开始,现要求写一个求1+2+3+..+100的结果的程序,那我可以这样写:
int count = 100;
int sum = 0;
for (int i =1; i <= count; i++)
{
sum += i;
}
这就是最简单的程序之一,这就是算法。但是它是最优的吗?是最高效的吗?
儿时数学家高斯提出了另一种解法,他将两组1+2+3+..+100一组升序,一组降序进行组合,变成(1+100)+(2+99)+...(100+1),像这样:
最后得到的公式就是后世的等差数列求和公式(首项 + 末项)x 项数 / 2):
这样用程序来实现就是这样:
int count = 100;
int sum = 0;
sum = (1 + count) * count / 2;
这样的话,程序由运行一百次,就变成了运行一次,这就是更高效的算法。
什么是算法呢?算法就是描述解决问题的方法。
「算法是解决特定问题求解步骤的描述,在计算机中表表现为指令的有限序列,并且每条指令表示一个或多个操作。」
算法具有五个基本特性:「输入」、「输出」、「有穷性」、「确定性」和「可行性」。
一个合格的算法要基本符合这些要求,例如「正确性」,「可读性」,「健壮性」,「时间效率高和存储量低」。
正确性:「算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案」。但是算法的“正确”通常在用法上有很大的差别,大体分为以下四个层次。
对于这四层含义,层次1要求最低,但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱,不能算是生活幸福一样。而层次4是最困难的,我们几乎不可能逐一验证所有的输入都得到正确的结果。因此算法的正确性在大部分情况下都不可能用程序来证明,而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的,代价非常昂贵。所以一般情况下,我们把层次3作为一个算法是否正确的标准。
可读性:「算法设计的另一目的是为了便于阅读、理解和交流。」可读性高有助于人们理解算法,晦涩难懂的算法往往隐含错误,不易被发现,并且难于调试和修改。
我们写代码的目的,一方面是为了让计算机执行,但还有一个重要的目的是为了便于他人阅读,让人理解和交流,自己将来也可能阅读,如果可读性不好,时间长了自己都不知道写了些什么。可读性是算法(也包括实现它的代码)好坏很重要的标志。
一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。
健壮性:「当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。」
时间效率指的是算法的执行时间,对于同一个问题,如果有多个算法能够解决,执行时间短的算法效率高,执行时间长的效率低。
存储量需求指的是算法在执行过程中需要的最大存储空间,主要指算法程序运行时所占用的内存或外部硬盘存储空间。「设计算法应该尽量满足时间效率高和存储量低的需求」。
「这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低」。
但是有缺陷:
在计算机程序编制前,依据统计方法对算法进行估算。
经过分析,一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:
第1条当然是算法好坏的根本,第2条要由软件来支持,第4条要看硬件性能。也就是说,抛开这些与计算机硬件、软件有关的因素,「一个程序的运行时间,依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少」。
函数的渐近增长是指当自变量趋近于正无穷时,函数增长的趋势。通俗来说,可以想象一条直线在平面上向右无限延伸,而函数就是这条直线上的一个点,当自变量趋近于正无穷时,函数的值会随着自变量的增加而增加。而函数的渐近增长就是描述这个增长的速度和趋势。
举个例子,如果一个函数的渐近增长是线性的,那么当自变量增加一单位时,函数的值也会增加一单位,这种增长趋势可以用直线来描述。而如果一个函数的渐近增长是指数级的,那么当自变量增加一单位时,函数的值会增加很多单位,这种增长趋势可以用指数函数来描述。
在算法分析和计算机科学中,函数的渐近增长非常重要,因为它可以帮助我们预估算法的时间复杂度和空间复杂度,从而优化算法的效率。通过对函数的渐近增长的分析,我们可以找到最优的算法实现方式,以达到最快的运行速度和最少的资源消耗。
在进行算法分析时,「语句总的执行次数
是关于问题规模
的函数,进而分析
随
的变化情况并确定
的数量级」。
「算法的时间复杂度,也就是算法的时间量度,记作:
。它表示随问题规模n的增大,算法执行时间的增长率和
的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中
是问题规模
的某个函数」。
这样用大写
来体现算法时间复杂度的记法,称之为「大O算法」。
一般情况下,随着
的增大,
增长最慢的算法为最优算法。
在计算机科学中,大O表示算法的渐进复杂度。它是用来描述算法的时间或空间复杂度的一种方式。当我们说一个算法的复杂度为
时,我们指的是当输入大小为
时,算法的运行时间或空间复杂度与
成正比。通常,我们会使用最高阶的项来表示算法的复杂度,因为它在输入趋近于无穷大时最能反映算法的增长率。
「推导算法的时间复杂度」通常可以通过以下步骤来实现:
「推导大O阶方法」:
推导大O阶的过程涉及到分析算法的每个步骤的时间复杂度,并计算这些步骤的总时间复杂度。最终,我们将得到一个表示算法复杂度的数学表达式。例如,如果我们正在分析一个简单的循环,其中每次迭代的时间复杂度为
,并且循环执行
次,则总时间复杂度为
。如果我们分析的是一个递归算法,那么我们需要使用递归方程来推导出算法的复杂度。
推导大O阶需要对算法的实现细节有深入的理解,以便能够准确地计算每个步骤的时间复杂度,并最终得出算法的总时间复杂度。
常见的时间复杂度如下所示:
常用的时间复杂度所消耗的时间从小到大排序为
<
<
<
<
<
<
<
<
我们查找一个有个随机数字数组中的某个数字,最好的情况是第一个数字就是,那么算法的时间复杂度为
,但也有可能这个数字就在最后一个位置上待着,那么算法的时间复杂度就是
,这是最坏的一种情况了。
「最坏情况运行时间是一种保证,那就是运行时间将不会再坏了。在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况的运行时间。」
而平均运行时间也就是从概率的角度看,这个数字在每一个位置的可能性是相同的,所以平均的查找时间为
次后发现这个目标元素。
「平均运行时间是所有情况中最有意义的,因为它是期望的运行时间」。也就是说,我们运行一段程序代码时,是希望看到平均运行时间的。可现实中,平均运行时间很难通过分析得到,一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析,一种方法是计算所有情况的平均值,这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度,这种方法称为最坏时间复杂度。「一般在没有特殊说明的情况下,都是指最坏时间复杂度」。
算法的空间复杂度是指在算法执行过程中所需要的内存空间大小,通常用空间复杂度来衡量算法所占用的内存资源大小。算法空间复杂度的计算公式记作:
,其中,
为问题的规模,
为语句关于
所占存储空间的函数。
「错误思想」:
认为现在CPU速度越来越快,内存越来越大,算法的细微的优劣是用户体验不到的。
「数据验证」:
假设CPU在短短几年间,速度提高了100倍,这其实已经很夸张了。而我们的某个算法本可以写出时间复杂度是
的程序,却写出了
的程序,仅仅因为容易想到,也容易写。即在
的时间复杂度算法程序下,速度其实只提高了10倍(
=10),而对于
时间复杂度的算法来说,那才是真的100倍。
「结论」:
也就是说,一台老式CPU的计算机运行
的程序和一台速度提高100倍新式CPU运行
的程序。最终效率高的胜利方却是老式CPU的计算机,原因就在于算法的优劣直接决定了程序运行的效率。
❝参考资料 [1] 大话数据结构 / 程杰 著. --北京:清华大学出版社,2011.6 ❞
本文分享自 Niuery Diary 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!