# 算法入门

# 时间复杂度

大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)
上次更新: 8/9/2021, 11:55:32 AM