算法的速度
- 算法的速度指的并非时间，而是操作数的增速。谈论算法的速度时，指随着输入的增加，其运行时间将以什么样的速度增加；
- 算法的运行时间可以用大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），散列表是提供这种功能的方式之一；
网友评论