什么是搜索算法？

一种寻找的方法

• 在哪里搜？搜索空间 search space，collection of items
• 搜什么？一个或一组元素，an item or group of items
• 依据什么？特征属性，with specific propertities

搜索空间一定是具体的吗？

具体：电子病例

抽象：整数集

说 e in li 的算法复杂度 “至好” 是线性的逻辑是什么？

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

• 最坏输入数据情况下，e 不在 L 里，执行 O(len(L)) 次测试。
• 各次测试都是常数时间吗？如果是，那么才可以说复杂度与 len (L) 是线性关系。
• 各次测试分为找到 Li 与比较。
• 元素比较是常数时间。
• 找到各个 L[i] 是常数时间吗？
• 我们默认系统找到对应地址的内容（从某个地址里提取元素）这个动作是常数时间。
• 那么问题简化为：Python 能否在常数时间内计算出下一个元素的地址。

Python 怎样实现在常数时间里顺序索引元素？

先假想一个理想情况： - 一个 list，每个元素都是 int。 - 在内存中顺序存储。 - 因为每个整数是 1 字长 byte 占 4 个或 8 个字节 bit（32 位处理器或 64 位，硬件决定） - 计算索引地址：start+4*i

真实情况类似：列表的表现方式是 “长度 + 指针 1 + 指针 2+…” - 指针就是固定长度的，有的 32 位，有的 64 位。 - 指针所指向的地址里，才是任意类型的元素。 - 计算索引地址：start+4+4*i。


Python 对 List 的表示方式体现什么计算机技术？

间接引用，indirection 不直接：想要接触一个东西，先接触另一个东西，后者包含引用前者。

上面的写法有点生硬，我是不是可以翻译成下面这样。

托关系：不直接递红包，找认识人，建立信任保留回旋余地。

1950 年代开始，计算机科学家发现，这种方法可以解开很多问题。

用 variable 与 index 都是 indirection 的方式之一。

在集合中查找元素至少是线性复杂度吗？

一般来说，O (len (L)) 是最好的程度，因为必须遍历每个元素。

但是如果有附加信息，可以做的更快。

比如：集合中的元素排列有序，比如说升序排列。

• 从头开找，直到发现比 e 大的元素，就可以结束查找比较了，因为后面的元素也必定比 e 大，没有必要继续了。
  • 它可以改善平均运行时间；
  • 而不能改善最坏情况。
• 用二分查找，每次缩小一半可能空间。
  • 可以改善最坏情况。

二分查找建立在什么假设的基础上？

可能空间有序。 - 实数空间天然全盘有序。比如求平方根的算法。 - 在 specification 里要求函数调用者承担保证 list 集合有序的责任。 - 可以在函数内校验实际参数给的集合是否有序； - 但是校验有序性的动作，是 O (len (L)) 复杂度，失去用二分法降低复杂度的意义了。

干嘛要在 search 函数内还写函数？结果架空了 search 函数。

search 函数是 wrapper 包装 function，bSearch 是 helper 辅助 function。

因为 bSearch 的形式参数 low，high 只是实现方式，应该对使用者隐藏。

在 bSearch 这个递归函数里，递减函数有什么性质？在哪里体现？

类似于 while 循环的递减函数，这里：

1. 把行参对应的值映射为一个非负整数；
2. 这个值为 0，递归结束；
3. 递减函数的值随着每次递归都减小。

def search (L, e):
    """ 假设 L 是列表，其中元素按升序排列。
       如果 e 是 L 中的元素，则返回 True，否则返回 False"""

    def bSearch (L, e, low, high):
        #Decrements high - low
        if high == low: # 这里保证递减函数性质 2，到 0 停止递归。
            return L[low] == e
        mid = (low + high)//2
        if L[mid] == e:
            return True
        elif L[mid] > e:
            if low == mid: #整数除法向下取整，m 可能等于 l，而不可能等于 h，所以最后 else：L[mid] < e 的分支里，不用写 if 了。
                return False
            else:
                return bSearch (L, e, low, mid - 1) # 递减函数性质 3，递减。
        else:
            return bSearch (L, e, mid + 1, high) # 递减函数性质 3，递减。

    if len (L) == 0: # 这里保证递减函数的性质 1，非负。
        return False
    else:
        return bSearch (L, e, 0, len (L) - 1)

在 bSearch 的后半递归函数里，为什么要写 mid+1？

保证能够踩到递减函数为 0 的点，结束递归。仅此而已？仅此而已就不简单。

如果不做 - 1 和 + 1，看个实例

L =[0 1 2 3 4 5]
e = 2.5

1.
l = 0, h = 5
m = (0 + 5)//2 i.e 2
L [m=2] = 2 < e=2.5

2.
l = 2, h = 5
m = 3
L[m=3] = 3 > e=2.5

3.
l = 2, h = 3
m = 2
L[m=2] = 2 < e=2.5

4.
l = 2, h = 3
与上步相同，死循环。。。

可见，由于求 m 值的 // 向下取整，m 可能等于 l，如果在下一轮递归时 m 不加 1，就会陷入死循环。

但是前半递归函数的上限参数 mid-1 就没有那么复杂。 e 在 [L[low]，L[mid]）区间内，那么下一轮检验空间就可以写成 L[low:mid], 实际上末尾元素的 index 就是 mid-1。

def search (L, e):
    """ 假设 L 是列表，其中元素按升序排列。
       如果 e 是 L 中的元素，则返回 True，否则返回 False"""

    def bSearch (L, e, low, high):
        #Decrements high - low
        if high == low: # 这里保证递减函数性质 2，到 0 停止递归。
            return L[low] == e
        mid = (low + high)//2
        if L[mid] == e:
            return True
        elif L[mid] > e:
            if low == mid: #整数除法向下取整，m 可能等于 l，而不可能等于 h，所以最后 else：L[mid] < e 的分支里，不用写 if 了。
                return False
            else:
                return bSearch (L, e, low, mid - 1) # 递减函数性质 3，递减。
        else:
            return bSearch (L, e, mid + 1, high) # 递减函数性质 3，递减。

    if len (L) == 0: # 这里保证递减函数的性质 1，非负。
        return False
    else:
        return bSearch (L, e, 0, len (L) - 1)

为什么要费事做排序？

排序之后可以用更简单的搜索算法，前提是：

(排序 + 二分查找) 比 (直接查找) 节省。

sortComplexity (L) + log (len (L)) <len (L)

但是，排序不可能比 len (L) 还小，因为至少要遍历各个元素。

如果查找很多次呢？

sortComplexity (L) + klog (len (L)) 小于 klen (L) 呢？

可以分摊成本。 > It might make sense to pay the overhead of sorting the list once, and then amortize the cost of the sort over many searches.

选择排序的工作原理是什么？

维持一个循环不变量 / 式，loop invariant，满足： - 列表分成前缀部分 prefix（L[:i]）和后缀部分 suffix（L[i+1:]）； - 前缀部分已经排好序； - 前缀的每一个元素都不大于后缀部分中的最小元素。

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

归纳法可证上述代码能够保证循环不变式。

分而治之算法的特征是什么？

1. 递归基本情况。达到这个规模就好处理了，就不用再分化了。
2. 拆分的子问题的规模和数量。规模越小，数量越多。
3. 有办法合并子问题的解。

怎么描述归并排序的递归算法？

1. 如果列表的长度是 0 或者 1，那么它就不用排序了。
2. 如果列表的长度大于 1（至少是 2），那就将其分成两个列表，分别用归并排序处理。
3. 逐级合并排序好的结果。

为什么冯诺伊曼发现归并排序更快更好？

关键发现是：两个排好序的列表可以高效地合并为一个列表。

比较的次数是 O (len (L))，这里的 L 是两个列表中较长的那个。复制操作的次数是 O (len (L1) + len (L2))，因为每个元素都正好复制一次。

归并排序算法的实现？其计算复杂度分析？

def merge (left, right, compare):
    """ 假设 left 和 right 是两个有序列表，compare 定义了一种元素排序规则。
       返回一个新的有序列表（按照 compare 定义的顺序），其中包含与
        （left+right）相同的元素。"""

    result =[]
    i,j = 0, 0
    # 两两比较，复制走一个，移动一个 index 而已。
    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 中元素的排序规则（默认小于号）
       返回一个新的具有 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)

一个 len (L) 的列表，被分割 log (len (L)) 次，每次合并的复杂度至多是 O (len (L))，所以 mergeSort 的时间复杂度是 O (n*log (n))。

归并排序与选择排序相比的优缺点？

优点是快。1 万个元素，一个是 1 亿，一个是 13 万。

缺点是占用空间。每次合并都需要复制一份，而选择排序只需要一个位子。

快速排序有什么特点？

1960 年代 Hoare 提出。

运行时间不确定，依赖于被排序列表中元素的相对顺序。最坏情况下的运行时间是 O (n^2)，但是期望运行时间是 O (n*log (n))，与归并排序相同。

空间复杂度低，只需要 log (n) 大小的额外空间。

Python 现在用的排序算法是什么？

timsort，由 Tim Peters 在 2002 年提出。最坏情况下，时间复杂度与归并排序相同，但是平均情况下，相当好。performs considerably better.

Python 的两个排序函数怎么用？

list.sort (key = ?, reverse = ?) sorted_keys = sorted (dict, key = ?, reverse = ?)

key = keyfunction，是 function 类型，它把要排序的元素映射为一个可以比较大小的数值，比如 len（lis）= n，比如 weight（item）= w.

在 n 个元素的数据集里搜索出 k 个元素，如果允许做一下预处理，比如先用归并排序，我们能做到的最好情况就是 O (nlog (n))+kO (log (n)) 吗？

不是。还可以把数据存成字典，检索时间与 n 无关。

dict 用什么技术实现检索时间与 n 无关？

a technique called hashing，散列技术。

• hash table，散列表。一个列表 list。用 index 找到元素，是常数时间。
• hash function，散列函数。把 key 转换为 hash table 这个 list 的 index 值。
• hash bucket，散列桶。作为散列表 list 的一个元素，本身是一个列表 list。多个元素落入同一个 hash bucket 的话，添加作为此 list 的元素。

为什么称为散列表 table？

纵向是可以通过 hash function 算出 index 值的 hash buckets，横向是在每个 hash bucket 内的重合 collision 元素。

形式类似：

The buckets are:
 []
 [(99740, 6), (61898, 8)]
 [(15455, 4)]
 []
 [(99913, 18), (276, 19)]
 []
 []
 [(63944, 13), (79618, 17)]
 [(51093, 15)]
 [(8271, 2), (3715, 14)]
 [(74606, 1), (33432, 3), (58915, 7)]
 [(12302, 12), (56723, 16)]
 []
 [(27519, 11)]
 [(64937, 5), (85405, 9), (49756, 10)]
 []
 [(17611, 0)]

解读用%作为散列函数的一个例子代码。

class intDict (object):
    """键为整数的字典"""

    def __init__(self, numBuckets):
        """创建一个空字典"""
        
        #numBuckets 是散列桶的数量，是一个整数，跟 dict 元素数量相关。
        # 不能太小，太小了容易重合得多，降低时间效率；
        # 也不能太大，太大了空 list 多，降低空间效率。
        
        #先把 hash table 这个空楼房搭起来
        self.buckets =[]
        
        #盖 numBuckets 层。
        self.numBuckets = numBuckets
        for i in range (numBuckets):
            self.buckets.append ([])


    def addEntry (self, key, dictVal):
        """假设 key 是整数。添加一个字典条目。"""
        
        #hashBucket 是一个列表，是 hash talbe 这个楼房的某一层。
        #求余 %，多大的数，都映射到[0～numBuckets) 区间内的整数
        hashBucket = self.buckets[key% self.numBuckets]
        
        #确认在本层里有没有这个 key，有则替换，没有就什么都没干。
        for i in range (len (hashBucket)):
            if hashBucket[i][0] == key:
                hashBucket[i] = (key, dictVal)
                return
                
        #确认过没有这个 key，没有 return，会执下面的追加动作。   
        hashBucket.append ((key, dictVal))


    def getValue (self, key):
        """ 假设 key 是整数。
           返回键为 key 的字典值 """
        
        #先通过 hash function 换算出楼层号   
        hashBucket = self.buckets[key% self.numBuckets]
        
        #再搜寻此楼层的各个房间，有则告知，无则 None
        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

怎样减少 collision？

让 hash function 的 many-to-one mapping 做到各个输出值的机会均等，充分利用各楼层。

uniform distribution

被 hash function 映射到同一楼层怎么办？

楼层有房间，顺序排进去。

dict 中的元素真的没有顺序吗？

有顺序，可以按照楼层号和房间顺序打印。

但是突破了 abstraction barrier，严重违反 information hiding。

在 dict 中搜索的时间复杂度分析？

把 key 通过 hash function 找到楼层号，是 O (1)，在楼层内搜索元素，是 O (层内房间数)。所以，楼层越多，重合越少，越接近 O (1)。

trade space for time.

如何取舍？

以上，2018-04-24