在平坦的算法路上懵逼地曲折前进（一）

什么是算法？当我第一次接触到这个东西的时候，我产生了疑问。

其实算法就是解决问题的方法：

• 问题是什么？
• 我们有什么？
• 我们想得到什么？
• 尝试最简单的方式解决
• 看看如何改进

当我们在尝试写算法的时候，我们可能考虑到算法的效率问题，这个算法是否在不同情况都能保证它的效率，所以我们要对自己写出的算法有一个评估。

关于描述一个算法的复杂度，我们有下面这个图。

增长顺序：

• O(1)
• O(logn)
• O(n)
• O(nlogn)
• O(n^2)
• O(2^n)
  

随着输入越来越大，算法所运算的时间也会发生变化；用空间复杂度，时间复杂度来衡量一个算法。

注意：以下我们只考虑时间复杂度。

O(1)：

def square(x):
    return x * x
square(3)

O(n)：

def find_max(l):
    if l == None:
        return None
    mx = l[0]
    for n in l:
        if n > mx:
            mx = n
    return mx

O(n^2)：

def has_duplicate(l):
    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[i] == l[j]:
                return True
    else:
        return False

— Fibonacci：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

这个使用递归来求斐波拉契数列时间复杂度为 O(n^2)，因为再最后 return f(n-1) + f(n-2)，两个递归调用内有重复计算的地方。例如 n = 6，则递归为 fi(5) + f(4)，前一项递归为 f(4) + f(3)；后一项 f(3) + f(2)这样下去......，你会发现 f(4) 计算了2次，f(3) 计算了3次......，到最后你发现 f(1) 计算了7次。

改进版的算法（让其不用重复计算）：

def fibonacci2(n):
    assert(n>=0)
    if (n <= 1): 
        return (n,0)
    (a, b) = fibonacci3(n-1)
    return (a+b, a)

— Binary Search（a sorted list）

• Solution 1: Brute Force（匹配法）：

def search(num_list, val):
  
    if num_list == None:
        return -1
    
    for i in range(0, len(num_list)):
        if (num_list[i] == val):
            return i
    return -1

• Solution 2: Binary Search (递归法)：

def bi_serach_re(num_list, val):
    def bi_search(l, h):
 
        if l > h:
            return -1
        
        mid = (l + h) // 2
        if (num_list[mid] == val):
            return mid;
        elif (num_list[mid] < val):
            return bi_search(mid + 1, h)
        else:
            return bi_search(l, mid - 1)
        
    return bi_search(0, len(num_list))

• Solution 3: Binary Search (分治法)：

def bi_search_iter(num_list, val):
    l = 0
    h = len(num_list)
    while (l <= h):
        mid = (l + h) // 2
        if (num_list[mid] == val):
            return mid
        elif (num_list[mid] < val):
            l = mid + 1
        else:
            h = mid - 1
    return -1

Solution 2，3都是O(nlogn)，将数据查找时间都大大缩短了；例如：1—100里猜数的游戏，我们先猜50，这会让空间减半，下一次继续这样猜可以快速锁定。如果是1—100000，会猜多少次呢？

— Sorting

• Bubble sort（冒泡算法）

例如 [6, 3, 1, 5, 4, 4] 这样一个数列，相邻两个数比较，如果是前一个大于后一个则交换，所以得到第一个Pass：[3, 1, 5, 4, 3, 6]（此时6已经排好序了，循环了6次），第二个Pass是 [1, 3, 4, 2, 5, 6]（此时5、6已经排好序了，循环了5次），第三个Pass是 [1, 3, 2, 4, 5, 6]（此时4、5、6已经排好序了，循环了5次），第四个Pass是 [1, 2, 3, 4, 5, 6]（此时3、4、5、6已经排好序了，循环了5次），第五个Pass（不变）是 [1, 2, 3, 4, 5, 6]（此时2、3、4、5、6已经排好序了，循环了5次），第六个Pass（不变）是 [1, 2, 3, 4, 5, 6]（此时1、2、3、4、5、6已经排好序了，循环了5次）。

按照这样的思路我们可以得到：

def _bubble_sort(nums: list, reverse=False):
    import time
    start = time.time()
    for i in range(len(nums)):
       
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    if reverse:

        nums.reverse()
    t = time.time() - start
    return len(nums), t

def bubble_sorted(nums: list, reverse=False) -> list:
    """Bubble Sort"""
    nums_copy = list(nums)
    _bubble_sort(nums_copy, reverse=reverse)
    return nums_copy

l = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
l = bubble_sorted(l, reverse=True)
print(l)

• Insert sort（插入算法）：

例如 [3, 8, 2, 1, 7, 6, 5] 这样一个list，Pass1：前两个数比较顺序不变，Pass2：第二个和第三个数字比较交换位置 ([3, 2, 8, 1, 7, 6, 5])，‘2‘再与’3‘交换，这样使得前三项都为sorted了 ([2, 3, 8, 1, 7, 6, 5])，Pass3：’1‘和前面的已经sorted的数再进行插入比较 ([1, 2, 3, 8, 7, 6, 5])……

def insert_sort(items):
    for sort_inx in range(1,len(items)):
        unsort_inx = sort_inx
        while unsort_inx > 0 and items[unsort_inx-1] > items[unsort_inx]:
            items[unsort_inx-1], items[unsort_inx] = items[unsort_inx], items[unsort_inx-1]
            unsort_inx = unsort_inx-1
    return len(items)

这个的时间复杂度是O(n^2)

• Selsecion sort（选择算法）：

例如 [3, 8, 4, 2, 1, 6] 这样一个list，先找这个list的最小的index (以下简称minIdx)，这个minIdx=4，然后把第一个3和它交换位置 (pass1： [1, 8, 4, 2, 3, 6])，再找新的 minIdx=3,和第二个8交换位置 (pass1： [1, 2, 4, 8, 3, 6])……

def sort1(array):
    for i in range(len(array)):
        pos_min = i
        for j in range(i + 1,len(array)):
            if (array[j] < array[pos_min]):
                pos_min = j
        
        array[i],array[pos_min] = array[pos_min],array[i]
        return array

就类似这样去实现这个算法，这个比较简单(O(n^2)的复杂度

• Merge sort（合并算法）：
  

这个是令我非常头疼的算法，随便给你一个数组[3, 9, 6, 5, 8, 2, 4, 7]，我们先要利用分治法(DIvide and conque)进行拆分，[3, 9] [6, 5] [8, 2] [4, 7]，然后每组进行sort，得到[3, 9] [5, 6] [2, 8] [4, 7]，左边两个进行Merge，右边两个进行Merge，然后得到[3, 5, 6, 9]  [2, 4, 7, 8]，然后这个两个在进行大Merge，最终得到排好序的list。

这个Merge是如何实现的呢？

把 [3, 5, 6, 9] 设为 a[i] ，i 指向第一个数字

把 [2, 4, 7, 8] 设为 b[j] ，j 指向第一个数字

a[0] > b[0]，则把 b[0] append 到一个空 list 中去，然后 j+1；

a[0] < b[1]，则把 a[0] append 到上一个 list 中去，然后 i+1；

……

最后得到 [2, 3, 4, 5, 6, 7, 8, 9]

★注意：当i走到头了，j后面还有数字；也有可能j走到头了，i后面还有数字；这个时候就应该把多余的数字加到那个list后面。

所以我们写出了下面的代码：

def _merge(a: list, b: list) -> list:
    """Merge two sorted list"""
    c = []
    while len(a) > 0 and len(b) > 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
            
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

def _merge_sorted(nums: list) -> list:
 
    if len(nums) <= 1:
        return nums

    m = len(nums) // 2
    a = _merge_sorted(nums[:m])
    b = _merge_sorted(nums[m:])
    return _merge(a, b)

 
def merge_sorted(nums: list, reverse=False) -> list:
    import time
    start = time.time()
    """Merge Sort"""
    nums = _merge_sorted(nums)
    if reverse:
        nums = nums[::-1]

    t = time.time() - start
    return nums, len(nums), t

关于Sort就说到这里，剩下还有Quick Sort以及搜索算法将在在平坦的算法路上懵逼地曲折前进（二）上和大家讨论。

9