itjob就业培训java教材14

《itjob就业培训java教材14》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十四章：数据结构与算法（上）ITjob就业培训第十四章：数据结构与算法（上）学习目标n算法(algorithm)n算法的类型n查找算法n排序算法n递归(recursive)n阶乘递归(factorialrecursive)n快速排序245第十四章：数据结构与算法（上）ITjob就业培训算法(algorithm)：对一个现有的问题我们采取的解决过程及方法，可简单可复杂，可高效可低效。一个用算法实现的程序会耗费两种资源：处理时间和内存。很显然，一个好的算法应该是耗费时间少、所用内存低，但是，在实际中，我们往往不能两方面顾全!算法的效率分析标准：衡量算法是否高效主要是从以下几个方面

2、来分析：¨简单性和清晰度一般我们都希望算法越简单越清晰就越好，但是要保证效率为前提。可是，往往我们在复杂的项目开发中所遇见的问题比较复杂，对时间和空间效率的要求也较高，因此，算法一般都会比较复杂。¨空间效率注意：这里的空间效率并不是指算法代码占用的内存指令空间,而是指代码中的数据分配(变量与变量所引用值的分配)以及方法调用所使用的内存(调用栈的空间分配)。比如，我们常用的递归，虽然会使代码清晰简单，但是内存的使用也会大大提高。理想的，程序所使用的内存应该和数据及方法调用所占用内存相等。但事实总是会有些额外的开销！因此，空间效率也是我们衡量算法的方面之一。¨时间效率针对同一任务所

3、使用的不同算法所执行的时间都会不同。比如：在一个数据集合中查找数据，我们会从第一个数据开始查找，一直找到需要的数据为止，如果查找数据存在，则这种查找方式(称之为线性查找)一般要查找半个列表！然而，如果数据的排放是有序的，则通过另一种查找方法会更有效，即二分查找法，首先从集合的中间开始，如果查找值在中间值的前面，则从集合的前一半重复查找，否则从后一半查找，每执行一次则将查找的集合减少为前一次的一半。算法的类型：所有的算法可以大概分为以下三种类型：1．贪婪算法(greedyalgorithm)该算法每一步所做的都是当前最紧急、最有利或者最满意的，不会考虑所做的后果，直到完成任务。这

4、种算法的稳定性很差，很容易带来严重后果，但是，如果方向正确，那该算法也是高效的。2．分治算法(divide-and-conqueralgorithm)该算法就是将一个大问题分解成许多小问题，然后单独处理这些小问题，最终将结果结合起来形成对整个问题的解决方案。当子问题和总问题类型类似时，该算法很有效，递归就属于该算法。3．回溯算法(backtrackingalgorithm)也可以称之排除算法，一种组织好的试错法。某一点，如果有多个选择，则任意选择一个，如果不能解决问题则退回选择另一个，直到找到正确的选择。这种算法的效率很低，除非运气好。比如迷宫就可以使用这种算法来实现。实际上，

5、我们对算法的效率高低评价，主要是在时间和内存之间权衡。根据实际情况来决定，比如有的客户不在乎耗用的内存是多少，他在乎的是执行的速度，那么一个用内存来换取更高执行时间的算法可能是更好的。同样，有的客户可能不想耗用过多内存同时对速度也不是特别要求。不管怎样，效率是算法的主要特性，因此关注算法的性能尤其重要！标准的测量方法就是找出一个函数(增长率)，将执行时间表示为输入大小的函数。选择处理的输入大小来说增长率比较低的算法！245第十四章：数据结构与算法（上）ITjob就业培训计算增长率的方式：1．测量执行时间通过System.currentTimeMillis()方法来测试部分代码:

6、//测量执行时间staticvoidcalculate_time(){longtest_data=1000000;longstart_time=0;longend_time=0;inttestVar=0;for(inti=1;i<=5;i++){//算法执行前的当前时间start_time=System.currentTimeMillis();for(intj=1;j<=test_data;j++){testVar++;testVar--;}//算法执行后的当前时间end_time=System.currentTimeMillis();//打印总共执行时间System.out.

7、println("test_data="+test_data+""+"Timeinmsec="+(end_time-start_time)+"ms");//环后将循环次数加倍test_data=test_data*2;}}以上代码将分别计算出1000000、2000000、4000000...次的循环时间。缺点：Ø不同的平台执行的时间不同Ø有些算法随着输入数据的加大，测试时间会变得不切实际！2．指令计数指令---指编写算法的代码.对一个算法的实现代码计算执行指令次数。两种类型指令：不管输