数据结构笔记：算法简介
小Bob 小Bob Bob来啦
2020年09月18日 23:32 __ _ _ _ _
点击上方「 蓝字 」关注”程序员Bob”
每天与你不见不散！
每日一句，送给最珍贵的你：
我知道你会来，所以我等。
上次学到了算法，也只是简单的介绍了一下，接下来我们将有关算法的小知识学完，哈哈哈。
算法效率的度量方法
上篇数据结构文章中我们提到过 时间效率
，即在众多算法中要找出执行程序时间最短的那个，然后我们可以通过数据测试再利用计算机的计时功能，从而判断不同算法之间的效率是高还是低。
这里主要提供两种方法来计算不同算法的效率是高还是低。
NO.1：事后统计方法， 主要通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间来比较，从而确定算法效率的高低。
显然这种方法也是有很大的 缺点 的：
1，需要事先编好程序，耗费时间和精力，若错误，则浪费大把时间；
2，时间的比较依赖计算机硬件和软件的等环境因素，不同的计算机差异较大,且由于不同的操作系统，编译器，运行框架等软件的不同，也会影响他们的结果，甚至由于CPU和使用率和内存占用不同的情况，也会造成细微的差异；
3，算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在在小的测试数据中往往得不到体现。
基于以上的缺点，在度量算法效率时我们很少用到此方法。 ** NO.2:事前分析估算方法， ** 在程序编写前，依据传统方法对算法进行估算。
据分析，编写好的高级程序在计算机运行时所耗费的时间取决于下列因素：1，算法采用的策略，方法（算法好坏的根本）；
2，编译产生的代码质量（软件）；
3，问题的输入规模；
4，机器执行指令的速度（硬件）。
当然，最后想要检测算法的好坏，还是要靠算法的好坏和问题的输入规模。那么何为输入规模呢？输入规模是指输入量的多少。
比如下面两种代码：
第一种：
int i,sum=0,n=100; //执行1次for(i=1;i<=n;i++){ //执行n+1次sum=sum+i; //执行n次}printf("%d",sum); //执行1次//共执行2n+3
第二种：
int sum=0,n=100; //执行1次sum=(1+n)*n/2; //执行1次printf("%d",sum); //执行1次//共执行3次
**当我们把循环当作一个整体，忽略头尾循环判断的开销，那么我们就可以把这两个算法比作n次和1次的差距，这时我们便可以简单的判断算法之间的好坏。
**
上面说到的还只是常数阶，后面还会有更多的函数模型。
比如我们在循环时用到下面的语句：
int i,j,x=0,sum=0,n=100; //执行1次for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ x++; //执行n*n次 sum=sum+x; }}printf("%d",sum); //执行1次
我们可以清楚的看到上面的这个代码运行次数已经是n的平方次（忽略循环体头和尾的开销）。显然这个算法的执行时间随着n的增加也将远远多于上面的两个。
测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数，运行时间与计数成正比。
即在分析运行程序时，要把程序看成是独立于程序设计语言的算法或一系列步骤，最重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。
如下可以看出，当n值越来越大时，它们在时间效率上的差异也越来越大。
函数的渐近增长
渐近增长简单来说就是当我们函数最高次项的指数大时，函数随着n的增长，执行次数也会增长得特别快。也就是说，我们判断一个算法的效率时，
函数中的常数和其他次要项常常可以忽略，而更应该关注最高次项的阶数。
算法时间复杂度
在推算算法复杂度时，我们通常用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。
一般情况下，我们认为T(n)（总执行次数）在随着n的增大而增长最慢的我们称之为最优算法。
比如：O(1)叫常数阶，O(n)叫线性阶，O(n的平方)叫平方阶。
那么我们该怎么推导大O阶呢？？？
方法：
用常数1取代运行时间中的所有加法常数，
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项存在且不是1，则去除与这个项相乘的常数。最后得到的便是大O阶。
常数阶：
无论执行次数是10还是100，我们都记作O(1)，而不能是O(2),O(4)等任何数字，这也是很多初学者常常犯的错误。因为对于分支结构而言，无论是真还是假，执行的次数都是固定的，不会随着n的变大而发生变化，所以单纯的分支结构（不包含在循环结构中）其时间复杂度也是O(1)。
线性阶： 当循环体中的代码必须要执行n次时，那么它的循环的时间复杂度为O(n)。
对数阶：
int count=1;while(count<n){count=count*2;}
如上面一段代码，count每次乘以2以后，就离n更近了一分。最后可得2的x次方等于n，即x=Iog 2 n。所以此时间复杂度为O(Iogn)。
平方阶： 当我们有两层循环嵌套时，执行次数也为n*m。同理平方阶的时间复杂度为大O(n的平方)。
…
**到这里可以看出理解大O阶其实并不难，难的是对数列的一些相关运算，也更需要考虑到我们的 数学功底。 ** 常见的时间复杂度
常见时间复杂度所耗费的时间从小到大排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n的2次方) < O(n的3次方) <
O(2的n次方) < O(n!) < O(n的n平方)
最后在运行程序时我们总会遇到 最坏情况和平均情况
，最坏情况发生时运行时间便是一种保证，因为它的运行时间不会再坏了，所以在平时我们提到的运行时间都是最坏情况的运行时间。
但 平均情况下的平均时间往往是最有意义的 ，因为它是我们所期望的运行时间。所以说，计算所有情况的平均值这种我们一般称为平均时间复杂度。
而计算最坏情况下的时间复杂度，就叫做最坏时间复杂度。
算法空间复杂度
算法的空间复杂度通常通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n)),其中n为问题的规模，f(n)为语句的关于n所占存储空间的函数。
一般情况下，当一个程序在计算机上执行时，除了需要存储程序本身的指令，常数，变量和输入数据外，还需要存储对数据操作的存储单元。
若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。
若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
未完待续…
为你,千千万万遍.
关注 程序员Bob 公众号,与你一起终生学习
一键三连，就差你了
预览时标签不可点
阅读
__
