1、第十七课：数据结构 (上 ) 周甫 学习目标各种常用算法、排序算法的掌握 1递归算法 2快速排序算法 31 算法 (algorithm) v什么是算法 ?对一个现有的问题我们采取的解决过程及方法 ,即为算法 . 一个用算法实现的程序会耗费两种资源：处理时间和内存。v算法的效率分析标准 w简单性和清晰度w空间效率w时间效率v算法的类型w 贪婪算法 (greedy algorithm) w 分治算法 (divide-and-conquer algorithm) w 回溯算法 (backtracking algorithm) v计算增长率的方式w 1.测量执行时间通过 System.currentT
2、imeMillis()方法来测试*缺点：a.不同的平台执行的时间不同b.有些算法随着输入数据的加大，测试时间会变得不切实际！w2.指令计数指令 -指编写算法的代码 .对一个算法的实现代码计算执行指令次数。两种类型指令：不管输入大小，执行次数永远不变；执行次数随着输入大小改变而改变。一般，我们主要测试后一种指令。*w 3.代数计算代码 1：long end_time = 0; t1int testVar = 0; t2for (int i = 1; i = test_data; i+) t3testVar+; t4testVar-; t4假设 t1 - t4分别代表每条语句的执行时间，那么，以上
3、代码的总执行时间为： t1 + t2 + n(t3 + 2t4).其中 n = test_data,当 test_data增大时， t1和 t2可以忽略不计，也就是说，对于很大的 n,执行时间可以近似于： n(t3 + 2t4)w4.测量内存使用率一个算法中包含的对象和引用的数目，越多则内存使用越高，反之越低 v 比较增长率 w1.代数比较法条件 1： c f(n)/g(n) d(其中 c和 d为正常数， n代表输入大小 )当满足以上条件 1时，则 f(n)和 g(n)具备相同的增长率，或者两函数复杂度的阶相同！如： f(n) = n + 100 和 g(n) = 0.1n + 10上两函数就
4、具备相同的增长率。条件 2： 当 n增大时， f(n)/g(n)趋向于 0当满足此条件 2时，则该两个增长函数有不同的增长率。 比如： f(n) = 10000n + 20000 和 g(n) = n?2 + n + 1 。请比较以上两函数增长率是否一样，如果不一样，谁的增长率小？w2.大 O表示法 如果 f的增长率小于或者等于 g的增长率，则我们可以用如下的大 O表示法：f = O(g)O表示 on the order of将代码 1的代数增长率函数的大 O表达式如下：f(n) = t1 + t2 + n(t3 + 2t4)= a1*n + a= O(n)其中 a1 = t3 + 2t4; a = t1 + t2w3.最佳、最差、平均性能对每一个算法不能只考虑单一的增长率，而应该给出最佳、最差、平均的增长率函数 .2 查找算法 v1.线性查找从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。注意：要求被查找的数组中的元素是无序的、随机的。
