python编程导论 week5

算法复杂度

• 三种情况，最佳；最差；平均，根据墨菲定律考虑最差的情况
• 如果运行时间是一个多项式的和，那么保留增长速度最快的项，去掉其他各项； 如果剩下的项是个乘积，那么去掉所有常数
• 我们不关心对数的底数，因为对于某个对数来说，使用另一个底数的区别只相当于将原来底数的对数乘以一个常数

搜索算法

1、线性搜索

for i in range(len(L)):
    if L[i] == e:
        return True
    return False

2、假如我们对元素的存储顺序有所了解

• 仍是遍历，但对元素大小进行检查，最差情况算法复杂度不变O（n）

• 二分搜索法O(log(len(L)))

排序算法

1、选择排序 O(len(L)**2)

• 思想：迭代，前缀集合由空变满，后缀集合每次抽出最小数放到前缀集合

def selSort(L):
  """假设L是列表，其中的元素可以用>进行比较。
  compared using >.
  对L进行升序排列"""
  suffixStart = 0
  while suffixStart != len(L):
#检查后缀集合中的每个元素
  for i in range(suffixStart, len(L)):
    if L[i] < L[suffixStart]:
      #交换元素位置
      L[suffixStart], L[i] = L[i], L[suffixStart]
   suffixStart += 1

2、归并排序 len(L)*log(len(L))

分治算法思想：

• 一个输入规模的阈值，低于这个阈值的问题不会进行分解；
• 一个实例分解成子实例的规模和数量；
• 合并子解的算法

归并排序：

(1) 如果列表的长度是0或1，那么它已经排好序了；
(2) 如果列表包含多于1个元素，就将其分成两个列表，并分别使用归并排序法进行排序；
(3) 合并结果。

def merge(left, right, compare):
  """假设left和right是两个有序列表， compare定义了一种元素排序规则。
  返回一个新的有序列表（按照compare定义的顺序），其中包含与
  （ left+right）相同的元素。 """
  result = []
  i,j = 0, 0
  while i < len(left) and j < len(right):
    if compare(left[i], right[j]):
        result.append(left[i])
        i += 1
    else:
      result.append(right[j])
      j += 1
  while (i < len(left)):
    result.append(left[i])
    i += 1
  while (j < len(right)):
    result.append(right[j])
    j += 1
  return result
def mergeSort(L, compare = lambda x, y: x < y):
  """假设L是列表， compare定义了L中元素的排序规则
  on elements of L
  返回一个新的具有L中相同元素的有序列表。 """
  if len(L) < 2:
      return L[:]
  else:
    middle = len(L)//2
    left = mergeSort(L[:middle], compare)
    right = mergeSort(L[middle:], compare)
    return merge(left, right, compare)

散列表

• 字典使用一种称为“散列”的技术进行搜索，这种技术使得搜
  索时间几乎与字典大小无关
• 空间换时间
• 两个输入被映射为同一个输出时，我们称这种情况为碰撞
• 范围内出现每种输出的可能性都是相等的，这会使产生碰撞的可能性最小化
• 如果没有碰撞，复杂度就是O(1)，因为每个散列桶的长度
  都是0或1。但是，碰撞当然无法避免。如果所有键都被散列映射到同一个桶中，复杂度就是O(n)

实现键为整数的字典

class intDict(object):
    """键为整数的字典"""
  def __init__(self, numBuckets):
  """创建一个空字典"""
  self.buckets = []
  self.numBuckets = numBuckets
  for i in range(numBuckets):
     self.buckets.append([])
     
def addEntry(self, key, dictVal):
  """假设key是整数。添加一个字典条目。 """
  hashBucket = self.buckets[key%self.numBuckets]
    for i in range(len(hashBucket)):
      if hashBucket[i][0] == key:
        hashBucket[i] = (key, dictVal)
        return
    hashBucket.append((key, dictVal))
  
def getValue(self, key):
  """假设key是整数。
  返回键为key的字典值"""
  hashBucket = self.buckets[key%self.numBuckets]
  for e in hashBucket:
    if e[0] == key:
        return e[1]
    return None
  
def __str__(self):
  result = '{'
    for b in self.buckets:
        for e in b:
            result = result + str(e[0]) + ':' + str(e[1]) + ','
    return result[:-1] + '}' #result[:-1] omits the last comma