算法 QuickStart

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1k 阅读时长 ≈ 2 分钟

什么是算法？

从一个步骤开始，按照既定的顺序执行完所有的步骤，最终结束得到结果的一个过程。

  • 确定性，算法的每个步骤都是明确的，对结果的预期也是确定的
  • 有穷性，算法必须是由有限个步骤组成的过程，步骤的数量可以是几个，也可以是几百万个，但是必须有一个确定的结束条件
  • 可行性，一般来说我们期望算法得出的是正确的结果，这意味着算法的每个步骤都是可行的，只要有一个步骤不可行，算法就是失败的，或者不能被称为某种算法。
  • 输入和输出，算法总是要解决特定的问题，问题的来源就是算法的输入，期望的结果就是算法的输出。

程序 = 算法+ 数据结构.

将问题抽象为数学模型，输入输出方法和算法步骤是编写计算机算法程序的三大关键要素。对于非常复杂的问题，建立数学模型是很困难的事情，但是对简单的计算机算法而言，建立数学模型实际上就是设计合适的数据结构的问题，同时，输入输出方式和算法步骤的设计都是基于相应的数据结构设计的。

二进制计算

异或消除

a=0⊕a=a⊕00=a⊕aa=0 \oplus a= a \oplus 0 \newline 0=a \oplus a

由上面两个推导出：

a=a⊕b⊕ba=a \oplus b \oplus b

交换两个数

a=a⊕bb=a⊕ba=a⊕ba=a \oplus b \newline b=a \oplus b \newline a=a \oplus b \newline

移除二进制最后一个1

a=n∧(n−1)a=n \land (n-1)

获取二进制最后一个1

diff=(n∧(n−1))⊕ndiff=(n \land (n-1)) \oplus n

常见数据结构

数据结构优点缺点
数组插入快，通过下标可以快速取值查找删除慢(需要遍历)，大小固定
有序数组比普通的无序数组快删除和插入慢，大小固定
栈提供后进先出的存取方式除栈顶，存取其他项很慢
队列提供先进先出的存取方式除队头队尾，存取其他项很慢
链表插入快，删除慢查找慢
二叉树查找，插入，删除都快(需要保证树平衡)剔除算法复杂
红黑树查找，插入，删除都快，平衡树算法复杂
2-3-4树查找，插入，删除都快，平衡树，类似的树对磁盘存储有用算法复杂
哈希表如果关键字已知，存取极快，插入快删除慢，如果不知道关键字则存取很慢，存储空间使用不充分
堆插入，删除快，对最大，最小堆顶存取极值快其他数据项存取慢
图对现实世界建模有些算法慢且复杂

常见算法