《算法图解》读书笔记

发表于 | 分类于

读书计划开始了，这是我要阅读的第四本书

二分查找

对数

log2·8 表示将多少个 2 相乘才能等于 8。2 x 2 x 2 = 8，所以 log2·8 等于 3。

对数运算是幂运算的逆运算

代码

假设数据是从小到大排列的

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low + high) // 2  # // 表示向下取整
        guess = nums[mid]
        if guess > target:
            high = mid - 1
        elif guess < target:
            low = mid + 1
        else:
            return mid
    return None

二分查找的前提条件

仅当列表是有序的，二分查找才能管用

大 O 表示法

  • 算法的速度并非指时间，而是操作数的增速
  • 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加
  • O(log n) 比 O(n) 快，当需要搜索的元素越多时，前者比后者快得越多

选择排序

两种基本的数据结构：

  • 数组
  • 链表

一种排序算法：

  • 选择排序

内存的工作原理

把内存想象成储物格，每个储物格都有一个编号。要存东西的时候，找计算机要一个格子的编号，然后把东西存到这个编号的格子里面

对于数组

需要向计算机申请连续的储物格

对于链表

一个格子存有下一个格子的编号。所以向计算机请求储物格时，不要求连续，随机也可

优缺点

因为数组的内存地址是连续的。只要知道了第 0 个元素的内存地址，比如 000000，那么第 1 个元素就是 000001，第二个就是 000002，以此类推。因此数组的查找特别快。但是对于插入与删除，需要向后和向前移动后面的所有元素，因此速度比较慢

而对于链表。每个元素存有下一个元素的内存地址信息，所以查找需要从第 0 个元素找起，因此查找很慢。而对于插入与删除，仅仅是修改一下指向下一个元素的地址信息即可，所以很快

用大 O 表示法

用大 O 表示法来看

操作 数组 链表
查找 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

选择排序

简单解释：

两个容器 A 和 B，容器 A 存放未排序的元素，容器 B 存放已经排号顺序的元素。每次从容器 A 中找到最小的元素，放入容器 B。直到容器 A 为空为止

代码：

假设每个元素值都不重复，按照从小到大排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findSmallest(nums):
    min = nums[0]  # 最小的元素
    min_index = 0  # 最小的元素的索引
    for i in range(len(nums)):
        if nums[i] < min:
            min = nums[i]
            min_index = i
    return min_index

def select_sort(nums):
    result = []
    for i in range(len(nums)):
        min_index = findSmallest(nums)  # 找到最小的元素的索引
        result.append(nums.pop(min_index))  # 从容器 A 去除这个最小元素，加入容器 B 中
    return result

递归

递归条件和基线条件

编写递归函数时，要告诉它何时终止递归。所以有了：

  • 递归条件（recursive case）
  • 基线条件（base case）

递归条件就是函数自己调用自己。基线条件就是什么时候终止递归，以免形成死循环

栈

  • FILO
  • push
  • pop

调用栈

所有函数调用都会进入调用栈

快速排序

递归的基线条件

编写涉及数组的递归函数时，基线条件通常是数组为空或者只包含一个元素。陷入困境时，可以检查一下基线条件是不是这样的

计算数组元素之和

1
2
3
4
5
def sum2(nums):
    if nums == []:
        return 0
    else:
        return nums[0] + sum2(nums[1:])

计算数组元素个数

1
2
3
4
5
def count2(nums):
    if nums == []:
        return 0
    else:
        return 1 + count(nums[1:])

找出列表中最大的数字

1
2
3
4
5
6
7
8
9
10
def max(nums):
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return nums[1]
    else:
        if nums[0] > max(nums[1:]):
            return nums[0]
        else:
            return max(nums[1:])

二分查找，如果用循环来写

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search(nums, target):
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]
        if guess > target:
            high = mid - 1
        elif guess < target:
            low = mid + 1
        else:
            return mid
    return None

如果用递归来写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(nums, low, high, target):
    mid = (low + high) // 2
    if low <= high:
        guess = nums[mid]
        if guess > target:
            high = mid - 1
            return binary_search(nums, low, high, target)  # 另一半
        elif guess < target:
            low = mid + 1
            return binary_search(nums, low, high, target)  # 另一半
        else:
            return mid
    else:
        return None

调用

1
2
print(binary_search([1, 2, 4], 0, len(nums) - 1, 2))
print(binary_search([1, 2, 4], 0, len(nums) - 1, 6))

快速排序

1
2
3
4
5
6
7
8
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    else:
        pivot = nums[0]
        less = [i for i in nums[1:] if i <= pivot]
        greater = [i for i in nums[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

散列表

散列函数

含义：

无论给它什么数据，都返回一个数字

特点：

  • 相同的输入会得到相同的结果
  • 不同的输入会得到不同的结果

散列表（hash table）

散列表 = 散列函数 + 数组

利用散列函数得到元素在数组中的索引位置

速度很快，算法复杂度为 O(1)

冲突

散列函数得到的值有可能会相同

填装因子

填装因子 = 数组中被占用的位置数 / 数组长度

比如数组中有 2 个位置被占了，数组长度是 5，因此装填因子是 2/5，即 0.4。一旦填装因子大于 0.7，就调整散列表的长度

广度优先搜索

数据结构

  • 图
  • 队列

图的实现

用散列表

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import deque

def search(name):
    search_queue = dqueue()
    search_queue += graph[name]
    searched = []

    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + " is a mango seller")
                return True
            else:
                search_queue += graph[person]
                searched.add(person)
    return False