图解算法读书笔记

作者:刘专,日期:2018 年 02 月 04 日

《图解算法》作者是 Aditya Y. Bhargava,内容浅显易懂,他的个人博客 adit.io 干货内容不少,有丰富插图,十分有趣。本书在亚马逊有 kindle 版

本书代码使用 Python 2.7。

以下是读书笔记的内容。

1.2 二分查找

比如:登录 Facebook,核实账户是否存在。

对于包含 n 个元素的列表,用二分查找最多需要 步。

仅当列表是有序时,二分查找才管用。

def binary_search(list, item):
    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

运行时间

简单查找最多需要猜测的次数与列表长度相同,这被称为线性时间linear time)。

二分查找的运行时间为对数时间(或 时间)。

1.3 大 表示法

表示法指出算法有多快。比如,简单查找的运行时间为 ,二分查找法的运行时间是

1.3.4 一些常见的大 运行时间

2.1 内存的工作原理

计算机就像是很多抽屉的集合体,每个抽屉都有地址。

2.2 数组和链表

数组添加新元素的速度会很慢。而且必须是排列在一起。数组随机读取效率很高。

链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。犹如寻宝游戏。

链表无需移动元素。链表随机读的效率很低,需要从第一个元素开始读取。

常见的数组和链表操作的运行时间如下:

  数组 链表
读取
插入
删除

当需要在中间插入元素或删除元素时,链表是更好的选择。

当需要随机访问时,推荐使用数组。

REF