文档介绍：大学计算机-计算思维导论南京理工大学计算机学院冯元第四章算法与复杂性内容提要:、排序问题排序问题:现实世界中十分常见,如:在一类信息中查找某个特定信息。为提高搜索效率,需要先排序。结构化数据查找与统计中的排序问题非结构化数据查找与统计中的排序问题排序问题的复杂性在哪里?:本质是对一组对象按照某种规则进行有序排列。通常是把一组对象整理成按关键字递增(或递减)的排列,关键字是指对象的一个用于排序的特性。例如:对一组“人”,按“年龄”或“身高”排序;对一组“商品”,按“价格”排序;对一组“网页”,按“重要度”排序;对一组“词汇”,按“首字母”字典序排序。……?【算法A:未排序数据查找算法】,直到其最后一条记录为止,读取每一条记录,做Step2。,判断成绩是否等于给定的分数:如果是,则输出;如果不是,则不输出。Endofalgorithm学号姓名成绩120300101***88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73算法效率:读取并处理所有记录,即n条记录数据表记录数:***88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73算法效率:读取并处理所有记录,即n条记录数据表记录数:n【算法B:已排序数据查找算法】,直到其最后一条记录为止,读取每一条记录,做Step2和Step3步。,判断成绩是否等于给定的分数:如果等于,则输出;如果不等于,则不输出。:如果不是,则继续;否则,退出循环,算法结束。***88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73数据表记录数:n【算法C:已排序数据查找算法】,待查询区间的起始记录位置Start为1,终止记录位置Finish为n;=(Start+Finish)/2,读取第I条记录。:(1)如果是小于,调整Finish=I-1,如果Start>Finish则结束,否则继续做Step2;(2)如果是大于,调整Start=I+1,如果Start>Finish则结束,否则继续做Step2;(3)如果是等于,则输出,继续读取I周围所有的成绩与给定查找条件相等的记录并输出,直到所有相等记录查询输出完毕则算法结束。Endofalgorithm算法效率:除极端情况外读取并处理<=n/(文档)的查找和搜索需要排序图书馆或网上有大量文档,这些文档大小各不相同。如何快速地查找一份文档?如何确定一份文档是否包含给定的一个或多个“关键词”哪些词汇是一份文档的关键词?每当用户输入一个关键词,是否要扫描所有文档?:待排序的数据可一次性地装入内存中,即排序者可以完整地看到和操纵所有数据,使用数组或其他数据结构便可进行统一的排序处理。外排序问题:待排序的数据保存在磁盘上,不能一次性装入内存,即排序者不能一次完整地看到和操纵所有数据,需要将数据分批装入内存分批处理。(文档)的查找和搜索需要排序图书馆或网上有大量文档,这些文档大小各不相同。如何快速地查找一份文档?如何确定一份文档是否包含给定的一个或多个“关键词”哪些词汇是一份文档的关键词?每当用户输入一个关键词,是否要扫描所有文档?怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引