常用算法总结

发表于 | 更新于: | 分类于 | 阅读次数:

二分查找

给定一个数组（有序列表）和一个数字，要求查出该数字所在的索引位置。

def binary_search(list, item):
    # lowh和high用于跟踪要在其中查找的列表部分
    low = 0
    high = len(list) - 1
    
    # 只要范围没有缩小到只包含一个元素，就检查中间的元素
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        # 找到了元素
        if guess == item:
            return mid
        # 猜的数字大了
        if guess > item:
            high = mid - 1
        # 猜的数字小了
        else:
            low = mid + 1
    # 没有指定的元素
    return None

# 测试
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
print(binary_search(my_list, -1)) # => None

总结：

  • 二分查找是对数时间，时间复杂度为O(logn)
  • 简单查找是线性时间，时间复杂度为O(n)
  • O(logn)比O(n)快。需要搜索的元素越多，前者比后者就快越多
  • 算法运行时间并不以秒为单位
  • 算法运行时间是从其增速的角度度量的

选择排序

将数组元素按从小到大的顺序排列。

# 找出数组中的最小元素
def findSmallest(arr):
    # 存储最小的值
    smallest = arr[0]
    # 存储最小元素的索引
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest_index = i
            smallest = arr[i]
    return smallest_index

# 对数组进行排序
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        # 找出数组中最小元素的索引，并将其加入到新数组中
        smallest_index = findSmallest(arr)
        newArr.append(arr.pop(smallest_index)) # 原数组arr不断的删除最小的元素
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))

选择排序，每检查一次数组，找出最小元素，运行时间都为O(n)，而这个操作需要执行n次，因此其时间复杂度为O(n2)（其中的常数1/2要省略）

总结：

  • 需要存储多个元素时，可使用数组或链表
  • 数组的元素都在一起，链表的元素是分开的，其中每个元素都存储了下一个元素的地址
  • 数组的读取速度很快，链表的插入和删除速度很快

递归

基线条件和递归条件

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

countdown(5)

调用栈（call stack）

def greet2(name):
    print("how are you, ", name, "?")
    
def bye():
    print("ok bye!")
    
def greet(name):
    print("hello, ", name, "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()
    
greet("adit")

递归调用栈

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

说明：

  • 每个fact函数调用都有自己的x变量，但是不能访问其他函数调用的变量x
  • 最后一次被调用的函数先返回，然后接着返回之前的调用

总结：

  • 递归指的是调用自己的函数
  • 每个递归函数都有两个条件：基线条件和递归条件
  • 栈有两种操作：压入和弹出
  • 所有函数调用都进入调用栈
  • 调用栈可能很长，这将占用大量的内存

快速排序

分治算法（D&C算法）

# 循环求和
def sum(arr):
    total = 0
    for x in arr:
        total += x
    return total

print(sum([1, 2, 3, 4]))
# 递归求和
def sum(list):
    if list == []:
        return 0
    return list[0] + sum(list[1:])

print(sum([1, 2, 3]))
# 递归计算列表包含的元素数
def count(list):
    if list == []:
        return 0
    return 1 + count(list[1:])

print(count([1, 2, 3]))
# 递归找出列表中最大的数字
def max_(lst):
    if len(lst) == 0:
        return 0
    if len(lst) == 1:
        return lst[0]
    else:
        sub_max = max_(lst[1:])
        return lst[0] if lst[0] > sub_max else sub_max
    
print(max_([1, 2, 5, 3]))

快速排序

def quicksort(array):
    # 基线条件：为空或只包含一个元素的数组是“有序”的
    if len(array) < 2:
        return array
    else:
        # 递归条件
        pivot = array[0]
        # 由所有小于基准值的元素组成的子数组
        less = [i for i in array[1:] if i <= pivot]
        # 由所有大于基准值的元素组成的子数组
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
    
print(quicksort([10, 5, 2, 3]))

总结：

  • D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组
  • 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)
  • 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在
  • 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)快得多

散列表

# 散列表
book = {"apple": 0.67, "milk": 1.49, "avocado": 1.49}
print(book)
print(book["apple"])
# 散列表防止重复
voted = {}
def check_voter(name):
    if voted.get(name):
        print("kick them out!")
    else:
        voted[name] = True
        print("let them vote!")
        
check_voter("tom")
check_voter("mike")
check_voter("mike")

总结：

  • 散列表的查找、插入和删除速度都非常快
  • 散列表适合用于模拟映射关系
  • 散列表可用于缓存数据（例如，在Web服务器上）
  • 散列表非常适合用于防止重复

广度优先搜索

广度优先搜索解决了两类问题：

  • 第一类问题：从节点A出发，有前往节点B的路径吗？
  • 第二类问题：从节点A出发，前往节点B的哪条路径最短？
from collections import deque

def person_is_seller(name):
    return name[-1] == 'm'

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def search(name):
    # 创建一个队列
    search_queue = deque()
    # 将你的邻居都加入到这个搜索队列中
    search_queue += graph[name]
    # 这个数组用于记录检查过的人
    searched = []
    while search_queue:
        # 只要队列不为空，就取出其中的第一个人，并从队列中移除
        person = search_queue.popleft()
        # 仅当这个人没检查过时才检查
        if person not in searched:
            # 检查这个人是否是芒果销售商
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                # 不是芒果销售商。将这个人的朋友都加入搜索队列
                search_queue += graph[person]
                # 将这个人标记为检查过
                searched.append(person)
    return False

search("you")

总结：

  • 广度优先搜索指出是否有从A到B的路径，如果有，广度优先搜索将找出最短路径
  • 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题
  • 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱
  • 无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约会，而rachel也与ross约会”
  • 队列是先进先出（FIFO）的，栈是后进先出（LIFO）的
  • 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列
  • 对于检查过的人，务必不要再去检查，否则可能导致无限循环

狄克斯特拉算法

对比广度优先搜索，狄克斯特拉算法采用了“加权图”的概念。

# the graph
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

# the costs table
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# the parents table
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    # 遍历所有的节点
    for node in costs:
        cost = costs[node]
        # 如果当前节点的开销更低且未处理过
        if cost < lowest_cost and node not in processed:
            # 就将其视为开销最低的节点
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# 在未处理的节点中找出开销最小的节点
node = find_lowest_cost_node(costs)
# 这个while循环在所有节点都被处理过后结束
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    # 遍历当前节点的所有邻居
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        # 如果经当前节点前往该邻居更近
        if costs[n] > new_cost:
            # 就更新该邻居的开销
            costs[n] = new_cost
            # 同时将该邻居的父节点设置为当前节点
            parents[n] = node
    # 将当前节点标记为处理过
    processed.append(node)
    # 找出接下来要处理的节点，并循环
    node = find_lowest_cost_node(costs)
        
print("cost from the start to each node:")
print(costs)

总结：

  • 广度优先搜索用于在非加权图中查找最短路径
  • 狄克斯特拉算法用于在加权图中查找最短路径
  • 仅当权重为正时狄克斯特拉算法才管用
  • 如果图中包含负权边，请使用贝尔曼福德算法

贪婪算法

# 需要覆盖的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

# 广播台覆盖的州
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()

while states_needed:
    # 覆盖了最多的未覆盖州的广播台
    best_station = None
    # 包含该广播台覆盖的所有未覆盖的州
    states_covered= set()
    for station, states_for_station in stations.items():
        # 计算交集，同时出现在states_needed和states_for_station中的州
        covered = states_needed & states_for_station
        # 该广播台覆盖的州比best_station多
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
            
    states_needed -= states_covered
    final_stations.add(best_station)
    
print(final_stations)

总结：

  • 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解
  • 对于NP完全问题，还没有找到快速解决方案
  • 面临NP完全问题时，最佳的做法是使用近似算法
  • 贪婪算法易于实现、运行速度快，是不错的近似算法

动态规划

# 最长公共子串
# 两个字母相同
if word_a[i] == word_b[j]:
    # 将当前单元格的值设置为左上方单元格的值加1
    cell[i][j] = cell[i-1][j-1] + 1
# 两个字母不同
else:
    # 值为0
    cell[i][j] = 0
# 最长公共子序列
# 两个字母相同
if word_a[i] == word_b[j]:
    # 将当前单元格的值设置为左上方单元格的值加1
    cell[i][j] = cell[i-1][j-1] + 1
# 两个字母不同
else:
    # 选择上方和左方邻居中较大的那个
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

总结：

  • 需要在给定约束条件下优化某种指标时，动态规划很有用
  • 问题可分解为离散子问题时，可使用动态规划来解决
  • 每种动态规划解决方案都涉及网格
  • 单元格中的值通常就是你要优化的值
  • 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题
  • 没有放之四海皆准的计算动态规划解决方案的公式

K最近邻算法

总结：

  • KNN用于分类和回归，需要考虑最近的邻居
  • 分类就是编组
  • 回归就是预测结果（如数字）
  • 特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字
  • 能否挑选合适的特征事关KNN算法的成败
------ 本文结束感谢您的阅读 ------
坚持原创技术分享，您的支持将鼓励我继续创作！