作业解析-python搜索算法

目录

1. 作业题目……………………………………………………………….

2. 作业目的 ……………………………………………………………….

3. 运行效果 ……………………………………………………………….

4. 实现过程 ……………………………………………………………….

5. 知识点巩固 ……………………………………………………………

6 知识拓展 ………………………………………………………………..

7 学习建议 ………………………………………………………………..

作业辅导解析

LAB_WORKSHEET_WEEK 1622-python-算法

4th April,2018[日期]

1.作业题目:设计一个搜索算法并评估性能

Input: L: list containing *N* sub-lists of length M. Each sub-list contains M numbers (floats or ints), and the first P elements of each sub-list can be assumed to have been sorted in ascending order (assume that P<M). L[i][:p] contains the sorted elements in the i+1th sub-list of L P: The first P elements in each sub-list of L are assumed to be sorted in ascending order target: the number to be searched for in L Output: Lout: A list consisting of Q 2-element sub-lists where Q is the number of times target occurs in L. Each sub-list should contain 1) the index of the sublist of L where target was found and 2) the index within the sublist where the target was found. So, Lout = [[0,5],[0,6],[1,3]] indicates that the target can be found at L[0][5],L[0][6],L[1][3]. If target is not found in L, simply return an empty list (as in the code below)

2.作业目的:

1、 掌握基本的搜索算法:顺序搜索、折半查找

2、 学会评估算法的性能,并通过实验进行验证

3.运行效果:

image

4.实现过程:

查找算法的过程: 对于数组中的每一行:

1. 前面的 P 个元素是有序的, 因此可以考虑使用二分查找,记录查找成功的结果。由 于前 P 个有序元素中可能存在多个连续的匹配项,因此还需要从第一个匹配元素开 始向两边顺序搜索,一旦不匹配则停止搜索,记录查找成功的结果。

2. 后面的 M – P 个元素是无序的,因此只能使用顺序查找,记录查找成功的结果

5.知识点巩固:

在计算机科学中,折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素 的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索

过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一 半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。

6.知识拓展: 计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个 关于代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述,不包括这个 函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入 值大小趋近无穷时的情况。

7.学习建议:

1. 读一下《算法导论》,尤其是算法复杂度相关理论,掌握分析评估一个算法的方法。

2. 动手实现常见的算法。