算法设计与分析
算法设计与分析
查找问题 ·问题：在一个列表中查找某个值 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
查找算法的比较 策略 一 -步数与n成正比 一称为线性时间算法 策略二 - 步数与log2n成正比 一称为对数时间算法 0 猜数游戏中：若数的范围是1~1000000，则 -策略一：平均要猜50万次才能猜对 人最坏1百万次，最好1次 -策略二：最坏也只需猜20次 Lu Chaojun,SJTU 6
Lu Chaojun, SJTU 6 查找算法的比较 • 策略一 – 步数与n成正比 – 称为线性时间算法 • 策略二 – 步数与log2 n成正比 – 称为对数时间算法 • 猜数游戏中:若数的范围是1~1000000,则 – 策略一:平均要猜50万次才能猜对 ©最坏1百万次,最好1次 – 策略二:最坏也只需猜20次
递归定义 ·两分查找算法的另一表述： 算法oinarySearch:在nums[low]~nums[high]中查找x mid (low high)/2 if low high x不在nums中 elif x nums [mid] 在nums[low]~nums[mid-1]中查找x else 在nums[mid+1]~nums[high]中查找x ·大问题的子问题仍是同样形式的问题，故 仍用解决大问题的算法来解决子问题 Lu Chaojun,SJTU 7
递归定义 • 两分查找算法的另一表述: 算法binarySearch:在nums[low]~nums[high]中查找x mid = (low + high) / 2 if low > high x 不在nums中 elif x < nums[mid] 在nums[low]~nums[mid-1]中查找x else 在nums[mid+1]~nums[high]中查找x • 大问题的子问题仍是同样形式的问题,故 仍用解决大问题的算法来解决子问题. Lu Chaojun, SJTU 7
递归定义的特征 ·递归定义完全是合法的，数学里有很多递 归定义的对象.如阶乘 n！=了1，当n=0 Ln*(n-1)!,否则 -这不是循环定义， 。递归定义的特征： -有奠基情形，这种情形无需递归； -每次递归都是针对较小情形， 一递归链最后终止于奠基情形 Lu Chaojun,SJTU 8
递归定义的特征 • 递归定义完全是合法的,数学里有很多递 归定义的对象.如阶乘: n ! = 1, 当n = 0; n * (n – 1) ! , 否则 – 这不是循环定义. • 递归定义的特征: – 有奠基情形,这种情形无需递归; – 每次递归都是针对较小情形; – 递归链最后终止于奠基情形. Lu Chaojun, SJTU 8
Python递归函数 ·例如：计算阶乘的递归函数 def fact (n): if n == 0: return 1 else: return n fact (n-1) Lu Chaojun,SJTU 9
Python递归函数 • 例如:计算阶乘的递归函数 def fact(n): if n == 0: return 1 else: return n * fact(n-1) Lu Chaojun, SJTU 9
递归查找算法 ·两分查找的递归版本： def recBinsearch(x,nums,low,high): if low high: return -1 mid (low high)/2 if x =nums [mid] return mid elif x nums [mid]: return recBinsearch(x,nums,low,mid-1) else: return recBinsearch(x,nums,mid+1,high) def search(x,nums): return recBinsearch(x,nums,0,len(nums)-1) Lu Chaojun,SJTU 10
递归查找算法 • 两分查找的递归版本: def recBinSearch(x, nums, low, high): if low > high: return -1 mid = (low + high) / 2 if x == nums[mid] return mid elif x < nums[mid]: return recBinSearch(x, nums, low, mid-1) else: return recBinSearch(x, nums, mid+1, high) def search(x, nums): return recBinSearch(x, nums, 0, len(nums)-1) Lu Chaojun, SJTU 10