week 5视频总结
效率和增长量级
程序运行耗费的时间和内存需要平衡
Problem is that this depends on:
- Speed of computer
- Specifics of Python implementa<on
- Value of input
算法复杂度
- 三种情况，最佳；最差；平均，根据墨菲定律考虑最差的情况
- 如果运行时间是一个多项式的和，那么保留增长速度最快的项，去掉其他各项； 如果剩下的项是个乘积，那么去掉所有常数
- 我们不关心对数的底数，因为对于某个对数来说，使用另一个底数的区别只相当于将原来底数的对数乘以一个常数
搜索算法
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
