时间复杂度

常数操作：和数量无关，每次都是固定时间内完成。
只要高阶项，也不要高阶项的系数。

选择排序、冒泡排序

选择排序：以第一位为起点，每次选择最小的数放在最前面，起点向后挪一位。
冒泡排序：相邻两位作比较，互换，大数放后。

异或运算

相同为0，不同为1。
等同于，无进位相加。
性质

例子
两数交换

注意：a、b内存中是两块位置，而不是一块位置。

题：
两个数有奇数个，其余数有偶数个，求这两个数？
思路：
全部异或，得到a异或b，这个数一定不为0，所以一定某位不为0。以此位为1、为0，分开。此位为1的所有数异或a异或b，得到a；剩余易求。

提取最右侧的1
取反，+1，与

插入排序

0位置有序，0-1位置有序，0-2位置有序…新数和前一个交换，直到队头。
插入排序优于选择排序、冒泡排序，原因是后两个是严格的O(n²)，而插入排序最坏是O(n²)，最好是O(n)

二分法

有序，找某数。
O(log₂n)，n/2/2/2/2…
算法中写为O(logN)，不写时代表以2为底。

例子
1.在一个有序数组中，找某数
2.在一个有序数组中，找>=某数最左的位置
3.局部最小问题

局部最小问题
无序数组，一个地方，左高、中低、右低，找出任何一个局部最小。
解：
先判断头，是否是局部最小；再判断尾，是否局部最小，若都不是，则中间必有局部最小…

对数器