【MIT 公开课】Computer Science and Programing Lession 10

    xiaoxiao2021-03-25  7

    一.分治算法:不断缩小问题的规模的算法。如二分法查找,归并排序。 如下是归并排序算法,主要思想为:先将一个列表分成左右两个列表,再左右分别继续分,直至分成每个列表中只有一个元素,再将两个列表进行归并排序,层层merge到最后左右两个列表进行merge。 def merge(left,right): """Assumes left and right are sorted lists. Returns a new sorted list containing the same elements as (left + right) would contain.""" result = [] i,j = 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 while (i < len(left)): result.append(left[i]) i = i + 1 while (j < len(right)): result.append(right[j]) j = j + 1 return result def mergesort(L): """Returns a new sorted list with the same elements as L""" print L if len(L) < 2: return L[:] else: middle = len(L) / 2 left = mergesort(L[:middle]) right = mergesort(L[middle:]) together = merge(left,right) print 'merged', together return together 复杂度为O(nlogn) 二.哈希算法:复杂度为常数的一个搜索算法,python实现字典的算法。是一种以空间换时间的算法 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。在构造这种特殊的“查找表” 时,需要选择一个“好”(尽可能少产生冲突)的哈希函数。 哈希算法的更多内容参考http://blog.csdn.net/tanggao1314/article/details/51457585 三.python的异常和断言 异常:try...except 断言:assert 断言是一句必须等价于布尔真的判定
    转载请注明原文地址: https://ju.6miu.com/read-200301.html

    最新回复(0)