数据结构和算法关系
但是，根据大学里边的概念性的东西来说，类似于我们学校，算法是单独开设课程，并不是和数据结构一起。所以，这一章还是理论。
高斯求和
int sum=0; int n=100; for(int i=0;i<=n;i++){ sum+=i; }
这样做确实没错，但是问题来了，你这和循环了多少次？如果没写错的话，是101次吧。为什么呢，因为你在每次累加的时候都会去走一遍for循环，这样就会平平增加不必要的时间去运算，你有这时间，你根本就抢不到亚索。
一共多少个101，100个吧，那如果去除2呢，结果不就是5050了。用代码怎么写？
int i=0; int sum=0 int n=100; sum=(1+n)*n/2
如果让你加到一亿呢？你想想哪种效率会更高。
算法定义
目前来说，普遍的定义就是：
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作
算法的特性
算法具有五个特性：输入、输出、有限、确定、可行
输入输出
这个比较好理解。算法具有零个或者多个输入。
有穷性
可行性
算法的每一步都是必须可行的，也就是说，每一步都能通过执行有限次数完成。
算法设计的要求
刚才我们说过，算法并不是唯一的。那我们在处理一个问题的时候，就必须要事先设计好算法才去解决问题。
正确性
算法的正确性是指算法至少应该具有输入和输出和加工厂处理无歧义性、能正确反映问题的需求、能狗得到问题得正确答案。
可读性
算法设计的另一目的就是为了方便阅读，理解和交流
你说你写一个很牛逼的代码，别人看不懂，，，怎么去承认你牛逼呢是不是
健壮性
当输入数据不合法时，算法也能做出相应的处理，而不是产生异常或者莫名奇妙的结果
时间效率高和存储量低
算法设计应该尽量满足时间效率高和存储量低的特点
这一点我迟迟没有达到。。。。
算法效率的度量方法
算法的效率指的就是算法的执行时间。那我们怎么去算一个他的执行时间呢？
最简单的方法其实就是用计算机的计时功能来计算不同算法的效率是高是低。
事后统计法
通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低
但是这种方法有很大的缺陷。
事前分析估算方法
在计算机程序编制前，依据统计方法对算法进行估算
经过分析发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于这些：
- 算法采用的策略、方法
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
所谓的输入规模就是输入量的大小；
第一种：
int sum=0; // 执行了1次 int n=100; // 执行了一次 for(int i=0;i<=n;i++){ // 执行了n+1次 sum+=i; // 执行了n次 }
第二种：
int sum=0; // 执行了一次 int n=100; // 执行了1次 sum=(1+n)*n/2; // 执行了1次
我们再看一个衍生算法：
int i; int j; int x=0; int sum=0; int n=100; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ x++; sum+=x; } }
这个例子很好理解，其实也就是多循环了一百次而已，那么最后算出的次数是多少呢？n²，没错吧
我们不关心程序用的什么语言，在什么机器上执行，只关心算法。最终在分析程序的运行时间时，最重要的是把程序堪称是独立于程序设计的算法或一系列步骤。
第一种总结出来就是f(n)=n；
第二种简单了，就是f(n)=1；第三种呢？f(n)=n²
函数的渐进增长
用一张表来演示一下：
看这张表，最后我们总结出算法a总体来说优于算法b
输入规模n在没有限制的情况下，只要超过一个数n，这个函数就总是大于另一个函数，我们称为是渐进增长
函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N使得队医所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的渐进增长快于g(n)
从中我们发现，随着n的增大，后面的+3还是+1其实不怎么影响最终的结果，所以我们可以去忽略这些常数。我们再看看第二个例子：
所以最后总结出，与最高次项的常数并不重要。
其实根据这两个表，大致都能分析出来，某个算法，随着n的增大，他会越来越优于另一种算法，或者越来越差于另一种算法
这其实就是事前估算方法的理论依据，通过算法时间复杂度来估算时间效率
算法时间复杂度
定义：在进行算法分析时，语句的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况而确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）=O(f(n))。他表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数；
总结
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/175.html