5 Python基本算法（ing）

5.1递归5.1.1基本情况的分析5.1.2动态规划 5.2搜索和排序5.2.1无序表搜索方式5.2.2有序表的搜索5.2.3哈希表

5.1递归

递归算法遵守三个原则，①所有的递归算法都有基本情况；②递归算法必须改变它本身的状态并且向基本情况靠近；③递归算法必须递归地调用自身。

5.1.1基本情况的分析

对比下面的两个将十进制100转化成二进制的程序，在分析的时候，可以把基本情况就是任何的余数都需要再进行一次二进制的转换，所以就嵌套调用了tostr()函数。

from pythonds import Stack def change(s,t): dig = "0123456789ABCDEF" st = Stack() rea = "" while s > 0: m = s%t st.push(m) s = s//t while not st.isEmpty(): rea = rea + dig[st.pop()] return rea print(chang(100,2)) from pythonds import Stack rstack = Stack() rea = "" def tostr(n,base): covstr = "0123456789ABCDEF" if n < base: rstack.push(covstr[n]) else: rstack.push(covstr[n % base]) tostr(n // base,base) tostr(8,2) while not rstack.isEmpty(): rea = rea + rstack.pop() print(rea)

5.1.2动态规划

动态规划在计算机中，是为了求解决策过程最优化的过程。以找零时使用最少个数的零钱来举例，零钱有100、50、20、10、5和1块的面值，假设拿10块钱买了3块钱的肥仔水，找零时当然是一张5块两张1块的零钱个数最少。我们在分析时，应该先从要找零的范围内最大面值的开始，然后看第二大面值的…依次查询。这种方法也叫“贪婪算法”，也就是动态规划的一种情况。

5.2搜索和排序

5.2.1无序表搜索方式

无序表只能通过依次的顺序搜索。

def sequentialSearch(alist, item): pos = 0 found = False while pos < len(alist) and not found: if alist[pos] == item: found = True else: pos = pos+1 return found

无序表的搜索时间复杂度是O(n)，因为目标在表内时，最好情况是1次就查到，最坏是n次才查到，平均是n/2，目标不在表内时，无论好坏都是查n 次，平均也就是n次。

5.2.2有序表的搜索

顺序搜索： def orderedSequentialSearch(alist, item): pos = 0 found = False stop = False while pos < len(alist) and not found and not stop: if alist[pos] == item: found = True else: if alist[pos] > item: stop = True else: pos = pos+1 return found 二分法搜索： def binarySearch(alist, item): if len(alist) == 0: return False else: midpoint = len(alist)//2 if alist[midpoint]==item: return True else: if item<alist[midpoint]: return binarySearch(alist[:midpoint],item) else: return binarySearch(alist[midpoint+1:],item)

5.2.3哈希表

哈希表也叫散列表，其中的每个存放元素位置称为槽，哈希表利用哈希函数来将表中的元素和所属位置对应起来。哈希表为了方便存储，通常都是利用字典来定义数据的，这样可以通过键来替代找值。 哈希表的哈希函数很多时候在运算规则上会导致不同的数据要存放到同一个槽里，为了避免这种冲突，