算法 QuickStart
算法 QuickStart
什么是算法？
从一个步骤开始，按照既定的顺序执行完所有的步骤，最终结束得到结果的一个过程。
- 确定性，算法的每个步骤都是明确的，对结果的预期也是确定的
- 有穷性，算法必须是由有限个步骤组成的过程，步骤的数量可以是几个，也可以是几百万个，但是必须有一个确定的结束条件
- 可行性，一般来说我们期望算法得出的是正确的结果，这意味着算法的每个步骤都是可行的，只要有一个步骤不可行，算法就是失败的，或者不能被称为某种算法。
- 输入和输出，算法总是要解决特定的问题，问题的来源就是算法的输入，期望的结果就是算法的输出。
程序 = 算法+ 数据结构.
将问题抽象为数学模型，输入输出方法和算法步骤是编写计算机算法程序的三大关键要素。对于非常复杂的问题，建立数学模型是很困难的事情，但是对简单的计算机算法而言，建立数学模型实际上就是设计合适的数据结构的问题，同时，输入输出方式和算法步骤的设计都是基于相应的数据结构设计的。
二进制计算
异或消除
a=0a=a0
0=a^a
由上面两个推导出：a=abb
交换两个数
a=a^b
b=a^b
a=a^b
移除二进制最后一个1
a=n&(n-1)
获取二进制最后一个1
diff=(n&(n-1))^n
常见数据结构
| 数据结构 | 优点 | 缺点 |
|---|---|---|
| 数组 | 插入快，通过下标可以快速取值 | 查找删除慢(需要遍历)，大小固定 |
| 有序数组 | 比普通的无序数组快 | 删除和插入慢，大小固定 |
| 栈 | 提供后进先出的存取方式 | 除栈顶，存取其他项很慢 |
| 队列 | 提供先进先出的存取方式 | 除队头队尾，存取其他项很慢 |
| 链表 | 插入快，删除慢 | 查找慢 |
| 二叉树 | 查找，插入，删除都快(需要保证树平衡) | 剔除算法复杂 |
| 红黑树 | 查找，插入，删除都快，平衡树 | 算法复杂 |
| 2-3-4树 | 查找，插入，删除都快，平衡树，类似的树对磁盘存储有用 | 算法复杂 |
| 哈希表 | 如果关键字已知，存取极快，插入快 | 删除慢，如果不知道关键字则存取很慢，存储空间使用不充分 |
| 堆 | 插入，删除快，对最大，最小堆顶存取极值快 | 其他数据项存取慢 |
| 图 | 对现实世界建模 | 有些算法慢且复杂 |