算法图解笔记

发表于 | 分类于 | | 阅读
算法相关的一些概念

递归函数的条件

def countDown(i):
    print(i)
    if i <= 0: # 基线条件
        return
    else:
        i -= 1
        countDown(i) # 递归条件

# countDown(3)

普通的选择排序

import time


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


# 1 选择排序 O(n × n)

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr
# cost: 1.1999999999998123e-05



arr = [1,2,4,7,0,3,-1]

start = time.perf_counter()
r = selectionSort(arr)
print(f"cost: {time.perf_counter() - start}")

print(r)

栈 与 调用栈（call stack）

栈有两种操作：压入和弹出

内存分配 -->> 栈(内存块)

    
greet2            栈2
name:  maggie

greet             栈1
name: maggie

栈1存储多个函数的变量，被称为调用栈

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

调用栈可能很长，这将占用大量的内存

def greet(name):
    print "hello, " + name + "!"
    greet2(name)
    print "getting ready to say bye..."
    bye()

def greet2(name):
    print "how are you, " + name + "?"

def bye():
    print "ok bye!"

递归函数factorial的调用栈

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)


r = fact(3)
print(r)

fact(3)

fact 
x    1                     1 
fact
x    2    -->  else        2 
fact
x    3    -->  else        3

尽量使用循环代替递归

分而治之（divide and conquer，D&C）——一种著名的递归式问题解决方法

D&C解决问题的过程包括两个步骤:

  • (1) 找出基线条件，这种条件必须尽可能简单。

  • (2) 不断将问题分解（或者说缩小规模），直到符合基线条件

快排实现

arr = [10,0,3,9,4]


def quickSort(arr):
    if len(arr) <= 1:
        return arr       # 基线条件
    else:
        pivot = arr[-1]   # 基准值 注意len(arr)<=1

        less = [i for i in arr[:-1] if i < pivot]
        greater = [i for i in arr[:-1] if i > pivot]

        return quickSort(less) + [pivot] + quickSort(greater)  # 递归条件

print(quickSort(arr))

常见的大O运行时间

算法 大O
二分 O(logn)
简单查找 O(n)
快排 O(nlogn)
选择排序 O(nxn)
旅行商问题 O(n!)

快排的平均情况 vs 最糟情况

快速排序的性能高度依赖于你选择的基准值

 最糟情况：  [1,2,3,4,...] 把有序数组第一位作为基准值， 调用栈层数 O(n) 
     O(n) (层数) x O(n) （元素个数） --  O(nxn)
 
 最优情况(也是平均情况):   总是将中间的元素用作基准值, 调用栈层数 O(log n), 
     O(log n)(层数) x O(n)  （元素个数） --  O(n log n)

散列表

散列表使用数组来存储数据

样本量 简单查询O(n) 二分查找O(logn) 散列表O(1)--常量时间
100 10s 1s 立即
1000 1.6m 1s 立即
10000 16.6m 2s 立即

散列函数(用于查找)

散列函数 将输入映射到数字

  • 散列函数总是将同样的输入映射到相同的索引

  • 散列函数将不同的输入映射到不同的索引

  • 散列函数知道数组有多大，只返回有效的索引

  • 好的散列函数很少导致冲突

    如果散列表存储的链表很长，散列表的速度将急剧下降

散列表的运用

  • 防止重复

  • 用作缓存 (常用的加速方式)

    缓存的工作原理：网站将数据记住，而不再重新计算


cache = {}
def get_page(url):
    if cache.get(url):
        return cache[url]   
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data

散列表 vs 数组 vs 链表

操作\数据类型 散列表(平均情况) 散列表(最差情况) 数组 链表
查找 O(1) O(n) O(1) O(n)
插入 O(1) O(n) O(n) O(1)
删除 O(1) O(n) O(n) O(1) 
在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速
度与链表一样快，因此它兼具两者的优点

需要避免冲突

较低的填装因子；

良好的散列函数。
  • 填装因子

填装因子 = 散列表包含的元素数量 / 位置总数

填装因子增大需要， 在散列表中添加位置 ， 即: 调整长度（resizing）

一旦填装因子超过0.7，就该调整散列表的长度
   
填装因子越低，发生冲突的可能性越小

调整散列表长度的工作需要很长时间
  • 良好的散列函数

良好的散列函数让数组中的值呈均匀分布

糟糕的散列函数让值扎堆，导致大量的冲突
Buy me a 肥仔水！