搜索、排序和复杂度分析

本文是《数据结构（Python语言描述）》Fundamentals of Python:Data Structure（作者Kenneth A. Lambert，译者李军）一书第三章的读书笔记。

1. 评估算法的性能

选择算法时，必须解决时间（运行速度）/空间（内存）的平衡问题。

评估算法的方式

2.搜索算法

2.1搜索最小值

def indexof_min(lyst):
    ''' Return the index of the minimum item'''
    minindex = 0
    current_index = 1
    while current_index < len(lyst):
        if lyst[current_index] < lyst[imnindex]:
            minindex = current_index
        current_index += 1
    return minindex

这个搜索最小值的算法复杂度是O(n)。对于一个大小为n的list, 它必须进行n-1次比较，才能找到最小值的位置。n-1次比较不会随着问题规模的放大而变化，也就是说是线性的，复杂度为O(n)。当然Python的内置函数min()的功能与此相同，这个自定义的函数肯定不会比min()更好用。

2.2搜索匹配项

# 顺序搜索(sequential search)或称线性搜索(linear search)

def line_search(target, lyst):
    positionn = 0
    while position < len(lyst):
        if target == lyst[position]:
            return position
        position += 1
    return -1

上面所说的搜索最小值的算法最好、最坏和平均情况是相同的，为达到目的，必须所有项都要比较一次。而顺序搜索（判断一个元素是否在集合中）最好的情况是O(1)，平均和最坏情况都是O(n)。

2.3有序列表的二叉搜索

对于那些没有按照任何特定的顺序排列的数据，顺序搜索是必要的。当搜索已经排序的数据时，可使用二叉搜索（又称二分搜索）。

def bi_search(target, sorted_list):
    left = 0
    right = len(sorted_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if target == sorted_list[mid]:
            return mid
        elif target < sorted_list[mid]
            right = mid - 1
        else:
            left = mid + 1
    return -1