《算法图解》读书笔记

《算法图解》读书笔记

我的有道云笔记-算法图解读书笔记

第一章 算法简介

基础
二分查找
算法运行时间–大O表示法
递归

二分查找

对于n个元素的有序列表,二分查找的最大次数为log_2n

算法运行时间-大O表示法

我们不仅需要知道算法的运行时间,还需要知道算法运行时间的增加速度
大O表示法指出了算法的运行速度,指出的是算法运行时间的增速
二分查找执行log_2n次操作:O(log n)
大O表示法指出了最糟糕情况下的运行时间–一种保证–运行时间不会超过它

一些常见的大O运行时间

O(log n)对数时间:二分查找
O(n)线性时间:简单查找
O(n*log n):
O(n^2):
O(n!):

一些要点:

  1. 算法的速度并非时间,而是操作数的增速

旅行商问题

一位旅行商要前往若干个城市,规划历经每个城市的最短旅程距离,需要n!次操作.运行时间为O(n!)

第二章 选择排序

基本数据结构:数组,链表
第一种排序算法

内存工作原理

内存相当于抽屉的集合体,每个抽屉都有其地址.将数据存储到内存时,向计算机请求存储空间,计算机给你一个存储地址.

数组和链表

数组是相连的区域,可能导致添加元素缓慢.如果预留空间可能造成内存浪费以及溢出预留空间后依旧有的效率低下的问题.
链表中的元素可以存储在内存里的任何地方.每个元素包含通往下一个元素的地址.
在插入元素方面链表更具优势.

数组

元素的位置称为索引

数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

O(n):线性时间
O(1):常量时间
仅当能够立即访问要删除的元素时,删除操作运行时间才为O(1)
随机访问,数组读取速度更快因为支持随机访问
顺序访问,链表只能顺序访问

选择排序

选择排序是遍历列表并找出最大(小)的,下一次找出次大(小)的,运行时间为O(nxn)或者O(n^2)

第三章 递归

递归
基线条件与递归条件

Leigh Caldwell 在Stack Overflow上说过:”如果使用循环,程序性能可能更高;如果使用递归,程序可能 更容易理解.”

基线条件和递归条件

递归函数的两部分:
基线条件(base case)和递归条件(recursive case)
基线条件:函数不再调用自己
递归条件:函数调用自己

调用栈(call stack)
栈只有两种操作:压入弹出
调用另一个函数时,当前函数暂停并处于未完成状态
栈占用大量内存,这时的两种选择:使用循环重新编写代码,使用尾递归

第四章 快速排序

学习分而治之
学习快速排序

分而治之

分而治之(divide and conquer, D&C) -一种著名的递归式问题解决方法
使用D&C解决问题的两个步骤:

  1. 找出基线条件,这种条件必须尽可能简单
  2. 将问题不断分解(或者缩小规模),知道符合基线条件

快速排序

基线条件:数组为空或只包含一个元素(无需排序)
D&C:将数组分解直到满足基线条件

  1. 首先选择一个元素作为基准值(pivot)
  2. 根据基准值分区(partitioning):小于基准值的子数组,基准值,大于基准值的子数组
  3. 对子数组进行快速排序

*合并排序(merge sort)*运行时间为O(n log n)
最糟情况下快速排序运行时间为O(n^2)
平均情况下O(n log n)

在大O表示法O(n)中,n实际上是c*n(其中c是算法所需的固定时间量常量,通常不考虑).
但有些时候常量影响很大,对于快速排序和合并排序就是这样.

平均情况和最糟情况

快速排序性能依赖于基准值选择.
调用栈的高度为O(log n)-调用栈的层数
最佳情况也就是平均情况,只要每次随机选择一个数组元素作为基准值.

第五章 散列表

学习散列表
学习散列表内部机制:实现,冲突和散列函数

散列函数

散列函数是这样的函数,即无论你给它什么数据,它都还你一个数字
或说:散列函数将输入映射到数字
散列函数的要求:

  1. 必须一致
  2. 将不同输入映射到不同数字

结合散列函数和数组创建了**散列表(hash table)**的数据结构.
散列表也被称为散列映射,映射,字典和关联数组.散列表的速度很快.
散列表由键和值组成,散列表将键映射到值.

冲突

散列函数很重要
如果使用的散列函数很好那么链表数组的链表就不会很长.

性能

散列表(平均情况) 散列表(最糟情况) 数组 链表
查找 O(1) O(n) O(1) O(n)
插入 O(1) O(n) O(n)
删除 O(1) O(n) O(n) O(1)

避开最糟糕情况需要避免冲突,则需要:

  • 较低的装填因子
  • 良好的散列函数

装填因子

装填因子=散列表包含的元素数/位置总数
一个经验规律:装填因子大于0.7则调整散列表长度.

第六章 广度优先搜索(breadth-first search, BFS)

新的数据结构 图来建立网络模型
学习广度优先搜索
学习有向图和无向图
学习拓扑排序

图简介

最短路径问题,解决思路被称为广度优先搜索
解决步骤:

  1. 使用图来建立问题模型
  2. 使用广度优先搜索

图由**节点(node)边(edge)**组成.一个节点与其他节点直接相连,这些节点被称为邻居.

广度优先搜索

广度优先搜索是一种用于图的查找算法,可以帮助回答两类问题:

  1. 从节点A出发有前往节点B的路径吗?
  2. 从节点A出发前往节点B的哪条路径最短

队列(queue)

队列是一种先进先出的数据结构(First in first out, FIFO),栈是一种后进先出的数据结构(Last in first out, LIFO)

实现图

有向图(directed graph)与无向图(undirected graph)
python中deque创建一个双端队列

第七章 狄克斯特拉算法

加权图
狄克斯特拉算法
图中的环->导致狄克斯特拉算法失效

狄克斯特拉算法包含四个步骤:

  1. 找出”最便宜”的节点
  2. 更新该节点邻居的开销
  3. 重复这个过程
  4. 计算最终路径

术语

权重 weight
带权重的图-加权图(weighted graph)
不带权重的图-(unweighted graph)
狄克斯特拉算法只适用于有向无环图(directed acyclic graph, DAG)
不能处理包含负权边的图.对于包含负权边的图可以使用另一种算法-贝尔曼-福德算法(Bellman-Ford algorithm)

第八章 贪婪算法

学习处理无快速算法的问题(NP完全问题)
学习识别NP完全问题
学习近似算法
学习贪婪策略

贪婪算法-每一步都选择局部最优解

背包问题

近似算法(approximation algorithm)-用于获得精确解的时间太长时使用,优劣标准:

  1. 速度
  2. 近似解与最优解的接近程度

NP完全问题

第九章 动态规划

cell[i][j]=max{cell[i-1][j],price now + cell[i-1][j-space used]}
调增粒度
仅当每个子问题都是离散,即不依赖于其他子问题时才能使用动态规划

第十章 K最近邻算法

欧几里得距离
余弦相似度(使用KNN需要了解)

第十一章 接下来如何做

二叉查找树

数组 二叉查找树
查找 O(log n) O(log n)
插入 O(n) O(log n)
删除 O(n) O(log n)

不能随机访问,平衡的特殊二叉树,例如红黑树
B树,红黑树,堆,伸展树

反向索引

傅里叶变换

Better Explained-一个数学阐述网站

并行算法

并行管理开销,负载均衡

MapReduce

分布式算法
Map(映射)Reduce(归并)

布隆过滤器和HyperLogLog

布隆过滤器是一种概率型数据结构,提供的答案有可能不对但是很可能正确.
概率型算法

SHA算法

Secure hash algorithm(安全散列算法,SHA)

局部敏感的散列算法

SHA是局部不敏感的.Simhash是局部敏感的,可以通过比较散列值来判断两个字符串的相似程度.

Diffie-Hellman密钥交换

  1. 双方无需知道加密算法,无需协商加密算法.
  2. 难以破解加密 使用两个秘钥,公钥和私钥

线性规划

Simplex算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注