《ITjob就业java教材14.doc》由会员分享，可在线阅读，更多相关《ITjob就业java教材14.doc（16页珍藏版）》请在金锄头文库上搜索。
1、第十四章：数据结构与算法（上） ITjob就业培训第十四章：数据结构与算法（上）学习目标n 算法(algorithm)n 算法的类型n 查找算法n 排序算法n 递归(recursive)n 阶乘递归(factorial recursive)n 快速排序算法(algorithm)：对一个现有的问题我们采取的解决过程及方法，可简单可复杂，可高效可低效。一个用算法实现的程序会耗费两种资源：处理时间和内存。很显然，一个好的算法应该是耗费时间少、所用内存低，但是，在实际中，我们往往不能两方面顾全!算法的效率分析标准：衡量算法是否高效主要是从以下几个方面来分析： 简单性和清晰度一般我们都希望算法越简单越清
2、晰就越好，但是要保证效率为前提。可是，往往我们在复杂的项目开发中所遇见的问题比较复杂，对时间和空间效率的要求也较高，因此，算法一般都会比较复杂。 空间效率注意：这里的空间效率并不是指算法代码占用的内存指令空间,而是指代码中的数据分配(变量与变量所引用值的分配)以及方法调用所使用的内存(调用栈的空间分配)。比如，我们常用的递归，虽然会使代码清晰简单，但是内存的使用也会大大提高。理想的，程序所使用的内存应该和数据及方法调用 所占用内存相等。但事实总是会有些额外的开销！因此，空间效率也是我们衡量算法的方面之一。 时间效率针对同一任务所使用的不同算法所执行的时间都会不同。比如：在一个数据集合中查找数据
3、，我们会从第一个数据开始查找，一直找到需要的数据为止，如果查找数据存在，则这种查找方式(称之为线性查找)一般要查找半个列表！然而，如果数据的排放是有序的，则通过另一种查找方法会更有效，即二分查找法，首先从集合的中间开始，如果查找值在中间值的前面，则从集合的前一半重复查找，否则从后一半查找，每执行一次则将查找的集合减少为前一次的一半。算法的类型：所有的算法可以大概分为以下三种类型：1贪婪算法(greedy algorithm)该算法每一步所做的都是当前最紧急、最有利或者最满意的，不会考虑所做的后果，直到完成任务。这种算法的稳定性很差，很容易带来严重后果，但是，如果方向正确，那该算法也是高效的。2
4、分治算法(divide-and-conquer algorithm)该算法就是将一个大问题分解成许多小问题，然后单独处理这些小问题，最终将结果结合起来形成对整个问题的解决方案。当子问题和总问题类型类似时，该算法很有效，递归就属于该算法。3回溯算法(backtracking algorithm)也可以称之排除算法，一种组织好的试错法。某一点，如果有多个选择，则任意选择一个，如果不能解决问题则退回选择另一个，直到找到正确的选择。这种算法的效率很低，除非运气好。比如迷宫就可以使用这种算法来实现。实际上，我们对算法的效率高低评价，主要是在时间和内存之间权衡。根据实际情况来决定，比如有的客户不在乎耗用的
5、内存是多少，他在乎的是执行的速度，那么一个用内存来换取更高执行时间的算法可能是更好的。同样，有的客户可能不想耗用过多内存同时对速度也不是特别要求。不管怎样，效率是算法的主要特性，因此关注算法的性能尤其重要！标准的测量方法就是找出一个函数(增长率)，将执行时间表示为输入大小的函数。选择处理的输入大小来说增长率比较低的算法！计算增长率的方式：1测量执行时间通过System.currentTimeMillis()方法来测试部分代码:/ 测量执行时间static void calculate_time()long test_data = 1000000;long start_time = 0;long
6、 end_time = 0;int testVar = 0;for (int i = 1; i = 5; i+)/ 算法执行前的当前时间start_time = System.currentTimeMillis();for(int j = 1; j = test_data; j+)testVar+;testVar-;/ 算法执行后的当前时间end_time = System.currentTimeMillis();/ 打印总共执行时间System.out.println(test_data = + test_data + n +Time in msec = + (end_time - star
7、t_time) + ms); /环后将循环次数加倍test_data = test_data * 2;以上代码将分别计算出1000000、2000000、4000000.次的循环时间。缺点： 不同的平台执行的时间不同 有些算法随着输入数据的加大，测试时间会变得不切实际！2指令计数指令-指编写算法的代码.对一个算法的实现代码计算执行指令次数。两种类型指令：不管输入大小，执行次数永远不变；执行次数随着输入大小改变而改变。一般，我们主要测试后一种指令。例：计算指令执行次数static void calculate_instruction()long test_data = 1000;int work
8、 = 0;for (int i = 1; i = 5; i+)int count = 0; for (int k = 1; k = test_data; k+)for(int j = 1; j = test_data; j+)/ 指令执行次数计数count+;work+;work-;System.out.println(test_data = + test_data + n +Instr. count = + count );test_data = test_data * 2;3代数计算代码1：long end_time = 0;t1int testVar = 0;t2for (int i =
9、 1; i = test_data; i+) t3testVar+;t4testVar-;t4假设t1 - t4分别代表每条语句的执行时间，那么，以上代码的总执行时间为：t1 + t2 + n(t3 + 2t4).其中n = test_data,当test_data增大时，t1和t2可以忽略不计，也就是说，对于很大的n,执行时间可以近似于：n(t3 + 2t4)4测量内存使用率一个算法中包含的对象和引用的数目，越多则内存使用越高，反之越低。比较增长率：1.代数比较法条件1：c f(n)/g(n) d (其中c和d为正常数，n代表输入大小)当满足以上条件1时，则f(n)和g(n)具备相同的增长率
10、，或者两函数复杂度的阶相同！如：f(n) = n + 100 和 g(n) = 0.1n + 10两函数就具备相同的增长率。条件2： 当n增大时，f(n)/g(n)趋向于0当满足此条件2时，则该两个增长函数有不同的增长率。比如：f(n) = 10000n + 20000 和 g(n) = n?2 + n + 1 。请大家比较以上两函数增长率是否一样，如果不一样，谁的增长率小？2大O表示法如果f的增长率小于或者等于g的增长率，则我们可以用如下的大O表示法：f = O(g)O表示on the order of将代码1的代数增长率函数用大O表达式如下：f(n) = t1 + t2 + n(t3 +
11、2t4)= a1*n + a= O(n)其中a1 = t3 + 2t4; a = t1 + t23最佳、最差、平均性能对每一个算法不能只考虑单一的增长率，而应该给出最佳、最差、平均的增长率函数查找算法：1线性查找从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。注意：要求被查找的数组中的元素是无序的、随机的。比如，对一个整型数组的线性查找代码：static boolean linearSearch(int target, int array)/ 遍历整个数组，并分别将每个遍历元素与查找值对比for (int i = 0; i array.l
12、ength; i+)if (arrayi = target)return true;return false;分析该算法的三种情况：a.最佳情况要查找的值在数组的第一个位置。也就是说只需比较一次就可达到目的，因此最佳情况的大O表达式为：O(1)b.最差情况要查找的值在数组的末尾或者不存在，则对大小为n的数组必须比较n次，大O表达式为：O(n)c.平均情况估计会执行：(n + (n - 1) + (n - 2) + . + 1)/n = (n + 1) / 2次比较，复杂度为O(n)2二分查找假设被查找数组中的元素是升序排列的，那我们查找值时，首先会直接到数组的中间位置(数组长度/2)，并将中间
13、值和查找值比较，如果相等则返回，否则，如果当前元素值小于查找值，则继续在数组的后面一半查找(重复上面过程)；如果当前元素值大于查找值，则继续在数组的前面一半查找，直到找到目标值或者无法再二分数组时停止。注意：二分查找只是针对有序排列的各种数组或集合代码：static boolean binarySearch(int target, int array)int front = 0;int tail = array.length - 1;/ 判断子数组是否能再次二分while (front target)tail = middle - 1;elsefront = middle + 1;return false;最佳情况：中间值为查找值，只需比较一次，复杂度为O(1)最差、平均：当我们对一个数组执行二分查找时，最多的查找次数是满足n 20因此可以得出二分法的最差及平均情况的复杂度为O(logn)。分析：1，2，3，4，5，6，7，8，9在上面数组中查找7需要比较多少次？查找2.5需要比较多少次？(假设存储的数值都是双精度数据类型)显然，对于一个有序数组或集合，使用二分查找会
