# 算法入门

# 时间复杂度

大O表示法能够比较操作数，指出了算法运行时间的增速

仅知道算法需要多长时间运行完毕还不够，还需知道运行时间如何随列表增长而增加
大O表示法指出了最槽糕情况下的运行时间
常见的大O运行时间
- O(logn)
- O(n)
- O(n*logn)
- O(n²)
- O(n!)

# 查找算法

# 二分查找

输入是一个有序的元素列表(从大到小 or 从小到大)，如果要查找的元素包含在列表中，返回其位置；否则返回NULL

def binary_search(search_list, item):
    # 从小到大 search_list, 查找item
    low, high = 0, len(search_list)

    while low <= high:
        mid = int((low + high) / 2)
        guess = search_list[mid]    # 主动猜测的计算逻辑，找中间的那个值
        
        if guess == item:
            return mid
        
        # 排除什么，余下什么
        elif guess > item:
            high = mid -1   
        else:
            low = mid + 1
    
    return None

# 排序算法

# 选择排序

def find_smallest(arr):
    """选择一个最小元素的索引"""
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < arr[smallest_index]:
            smallest_index = i
    return smallest_index


def selection_sort(arr):
    """"""
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))
    return new_arr

# 数据结构

数组在内存中的数据是相连的，而链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起

需要随机地读取元素时，数据的效率很高；相应的链表在插入和删除方面效率更高

# 递归调用

编写递归函数，必须告诉它何时停止递归，所以每个递归函数有两部分

基线条件(base case)，指的是函数不再调佣自己，从而避免形成无限循环
递归条件(recursive case)，指的是函数调用自己

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

# 快速排序

分而治之(divide and conquer, D&C)

def quick_sort(array):
    """
    快速排序 O(nlogn)
    """
    if len(array) < 2:
        # 基线条件：为空或只包含一个元素的数组是 "有序" 的
        return array

    else:
        # 随机选择一个元素作为一个基准值，快速排序的平均时间为 O(nlogn)
        pivot = array[0]
        
        # 由所有小于基准值得元素组成的子数组
        less = [i for i in array if i <= pivot]
        
        # 由所有大于基准值得元素组成的子数组
        greater = [i for i in array if i > pivot]
        
        return quick_sort(less) + pivot + quick_sort(greater)

# 其他算法

散列表

← 设计模式