算法设计与分析
算法设计与分析
查找问题 ·问题：在一个列表中查找某个值 def search (x,nums): #nums为一数值列表，x是一个数 #如果找到，返回x在列表中的位置 #否则返回-1 ·Python本身就提供有关的功能： -判断：x in nums -求位置：nums.index(x) Lu Chaojun,SJTU 2
Lu Chaojun, SJTU 2 查找问题 • 问题:在一个列表中查找某个值. def search(x, nums): # nums为一数值列表, x是一个数 # 如果找到,返回x在列表中的位置 # 否则返回-1 • Python本身就提供有关的功能: – 判断: x in nums – 求位置: nums.index(x)
策略一：线性查找 ·逐个检查列表中的数据. def search (x,nums): for i in range (len (nums)): if nums [i]==x: return i 上eturn-1 ·特点： 一适合无序数据列表 -不适合大数据量 人使列表有序后，线性查找算法可略加改进.(How?) Lu Chaojun,SJTU 3
Lu Chaojun, SJTU 3 策略一:线性查找 • 逐个检查列表中的数据. def search(x, nums): for i in range(len(nums)): if nums[i] == x: return i return –1 • 特点: – 适合无序数据列表 – 不适合大数据量 ©使列表有序后,线性查找算法可略加改进.(How?)
策略二：两分查找 ·猜数游戏：可取的策略？ 两分查找：每次查看有序列表的中点数据，根据 情况接着查找较大一半或较小一半. def search(x,nums): low,high 0,len(nums)-1 while low <high: mid (low high)/2 if x =nums [mid] return mid elif x nums [mid]: high mid -1 else: low mid 1 return -1 Lu Chaojun,SJTU 4
Lu Chaojun, SJTU 4 策略二:两分查找 • 猜数游戏:可取的策略? • 两分查找:每次查看有序列表的中点数据,根据 情况接着查找较大一半或较小一半. def search(x, nums): low, high = 0, len(nums) - 1 while low <= high: mid = (low + high) / 2 if x == nums[mid]: return mid elif x < nums[mid]: high = mid - 1 else: low = mid + 1 return -1
算法的优劣比较 ·经验分析 -根据电脑上的运行时间比较 0 抽象分析 -分析算法解题所耗"步数"（时间） 一步数又与问题难度相关 人查找问题中，问题难度用数据量n衡量 Lu Chaojun,SJTU 5
算法的优劣比较 • 经验分析 – 根据电脑上的运行时间比较 • 抽象分析 – 分析算法解题所耗"步数"(时间). – 步数又与问题难度相关 ©查找问题中,问题难度用数据量n衡量 Lu Chaojun, SJTU 5