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

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

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

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

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

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

增长顺序:

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

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

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

𝑂(1):

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

𝑂(n):

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

𝑂(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以及搜索算法将在在平坦的算法路上懵逼地曲折前进(二)上和大家讨论。

4

评论

评论

  • 一间生活 说道:
    发表于:2019-11-26 10:03

    在懵逼的阅读观看后懵逼地留下评论

    回复
  • 姜辰 说道:
    发表于:2019-11-27 10:36

    一脸懵逼的进来,然后出去。

    回复
  • rares 说道:
    发表于:2019-12-01 18:28

    听阿里某牛同学经常说某某某人算法很牛

    回复
6
分享

哦不,糟糕! 您的浏览器不支持。本网站针对这些浏览器进行了优化。请升级到支持的浏览器,并尝试再次加载网站。

立即升级