时间复杂度

• O(logn) : 出现在每次算法循环且规模减少一半的情况下，例如:

while n>1:
    print(n)
    n = n/2

• 常见的时间复杂度（按效率排序）：
  O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^2logn) < O(n^3)
• 简易判断时间复杂度

1. 确定问题的规模（n）
2. 循环减半过程 -> logn
3. k层关于n的循环 -> n^k

空间复杂度

1. 算法使用了几个变量 -> O(1)
2. 算法使用了长度为n的一维列表 -> O(n)
3. 算法使用了m行n列的二维列表 -> O(mn)

递归

1. 调用自身
2. 有结束条件

汉诺塔问题:

def hannuo_tower(n,a,b,c):
    if n == 1:
        print(a, '->', c)
    else:
        hannuo_tower(n-1, a, c, b)
        hannuo_tower(1, a,b ,c)
        hannuo_tower(n - 1, b, a, c)
hannuo_tower(3, 'A', 'B', 'C')

二分查找

前提：列表有序。思想：每次循环减半，注意区间边界值。

def binary_search(li, val):
    left = 0
    right = len(li) -1
    while left <= right:
        mid = (left + right) // 2 # 整除
        if li[mid] == val:
            return li[mid]
        elif val < li[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return None

排序

1. 排序lowB三人组：冒泡排序，选择排序，插入排序
2. 排序NB三人组：快速排序，堆排序，归并排序
3. 其他排序： 希尔排序，计数排序，基数排序

冒泡排序

关键点：每一趟产生一个最大/最小值，产生后的区成为有序区。写代码注意一下趟和无序区（指针指向无序区-1的位置）。

def bubble_sort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - 1 - i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
        print(li)
    return li

选择排序

关键点：每次选择一个最大/最小值在有序区列表的前面。写代码注意无序区最小值的位置

def select_sort(li): 
    for i in range(len(li) -1):
        min_ind = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_ind]:
                min_ind = j
        li[min_ind], li[i] = li[i], li[min_ind]
        print(li)
    return li

插入排序

关键点：有序区中默认有列表的第一个元素，从每次从无序区拿出一个元素与有序区进轮训行对比，注意元素的位移。

def insert_sort(li):
    for i in range(1, len(li)):
        j = i-1  # 默认左边的那个元素
        min_val = li[i]
        while j >= 0 and li[j] > min_val:
            li[j+1] = li[j] # 互换位置
            j-=1
        li[j+1]= min_val
        print(li)
    return li

快速排序

思路：

1. 取一个元素A（第一个元素），使得元素A归位。
2. 列表被A分为两部分，左边都比A小，右边都比A大。
3. 左右分别递归，完成排序。