binary search 二分法查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# 二分法查找, 返回数值在 list 中的位置, 否则返回 None
def binary_search(num_list, item):
    # 确定查找的数在列表中
    if item < num_list[0] or item > num_list[-1]:
        return None
    # 最小值位置
    low = 0
    # 最大值位置
    high = len(num_list) - 1

    while low <= high:
        # 中间位置, 向下取整
        mid = (low + hight) // 2
        if num_list[mid] < item:
            low = mid + 1
        elif num_list[mid] > item:
            high = mid - 1
        else:
            return mid
    return None

Big O notation 大 O 表示法

  1. Algorithm speed isn’t measured in seconds, but in growth of number of operations
  1. Instead, we talk about how quickly the run time of an algorithm increases as the size of the input increases
  1. Run time of algorithms is expressed in Big O notation
  1. O(log n) is faster than O(n), but it gets a lot faster as the list of items you’re searching grows

selection sort 选择排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def selection_sort(arr):
    def findSmallest(arr):
        smallest = arr[0]
        smallest_index = 0
        for i in range(1, len(arr)):
            if arr[i] < smallest:
                smallest = arr[i]
                smallest_index = i
        return smallest_index
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

def bubble_sort(arr):
    index = 0
    length = len(arr)
    for x in range(length):
        for y in range(x + 1, length):
            if arr[x] > arr[y]:
                arr[x], arr[y] = arr[y], arr[x]

divide & conquer 分而治之

在 1680m X 640m 的土地上如何划出最多均匀方块

以 640 为基准, 可以划出两个 640 * 640 的方块, 这样剩下的便是 640 * 400 的土地
再以 400 为基准, 可以划出一个 400 * 400 的方块, 这样剩下的便是一个 400 * 240 的土地
这样不断为一条较小边为基准画方块, 最后便可以得到最后一个 80 * 80 大小的方块, 这个长度便是最佳长度

将问题范围不断缩小后, 求出最简单问题的解, 然后用这个解去求原始问题的解, 递归使用这种思想

1
2
3
4
5
# n!
def fb(n):
    if n == 1:
        return 1
    return n * fb(n - 1)

快速排序法

快速排序法使用的便是一种分而治之的方

每次从数组中选出一个数(base), 把小于该数的放在左边数组, 大于的放在右边数组

分好之后, 再对左, 右两边的数组重复上一步

最后直到只有一个数时, 将这些数组依次组合起来

快速排序法的排序速度在于基数的选择

如若每次都选择到数组的中间大小值时, 需要递归层数是O(log n)

随机选择需要递归层数是O(n)

每层都需要比较n

最坏情况是O(log n<sup>2</sup>)

平均情况是O(nlog n), 也是最好情况

1
2
3
4
5
6
7
def quicksort(arr):
    if len(arr) < 2:
        return arr
    base = arr[0]
    smaller = [x for x in arr[1:] if x < base]
    greater = [x for x in arr[1:] if x > base]
    return quicksort(smaller) + [base] + quicksort(greater)