《算法图解》读书笔记1 （from 小白silen）

算法的速度

• 算法的速度指的并非时间，而是操作数的增速。谈论算法的速度时，指随着输入的增加，其运行时间将以什么样的速度增加；
• 算法的运行时间可以用大O表示法表示；
• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多；因此我们认为二分查找的速度比简单查找要快得多；
• 大O表示法 衡量的是算法在耗时最多情况下的运行时间；

---

数组和链表

• 需要将数据存储到内存时，计算机给我们一个存储地址，有2种基本方式：数组和链表；
  数组元素都是在一起的；
  链表中的元素可以存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在了一起；
• 针对元素的访问方式有2种：随机访问和顺序访问。常说数组的读取速度更快，因为其支持随机访问；
• 在同一个数组中，所有元素的类型都必须相同（都为int、double等）；

---

递归

• 递归指的是调用自己的函数。每个递归函数都有2个条件：基线条件（base case）和递归条件（recursive case），递归条件是指函数调用自己，而基线条件是指函数不再调用自己，从而避免形成无限循环；
• 递归只是让解决方案更清晰，并没有性能上的优势。实际上，如果使用循环，程序的性能可能更好；如果使用递归，程序可能更容易理解。
• 栈有2种操作：压入和弹出；所有函数都进入调用栈，调用栈可能很长，这将占用大量的内存；

---

D&C

• divide and conquer,D&C，是一种递归式问题解决方法；

  既然使用循环可以轻松地完成任务，仍然要在某些场合使用递归，因为诸如Haskell等函数式编程语言没有循环，因此只能使用递归来编写这样的函数；
  

• D&C将问题逐步分解，使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组

---

散列函数

• 散列表是一种功能强大的数据结构，其操作速度快
• 可以通过结合散列函数和数组来创建散列表；
• 散列表的查找、插入和删除速度都非常快；
• 散列表适合模拟映射关系；
• 一旦填装因子超过0.7，就该调整散列表的长度；
• 散列表可用于缓存数据（例如在web服务器上）；
• 散列表非常适合用于防止重复；
• 散列表用于大海捞针式的查找，例如将网站域名转化为IP地址，这个过程被成为DNS（DNS resolution），散列表是提供这种功能的方式之一；

---