10 算法
算法策略
分治法T(n)=O(nlogn)
将问题分解成规模较小、相互独立的子问题，各个击破，分而治之。
归并排序
将数列分为几个序列片段，逐趟两两归并，到底层归并成有序数列
最大子段和问题
动态规划法T(n)=O(nW)
将问题分解成互不独立子问题，保存子问题解，需要时再用，例如多项式时间算法
0/1背包问题
LCS最长公共子序列
贪心/贪婪法T(n)=O(n)
不从整体最优考虑，只根据当前信息选择某个标准，得到近似最优
背包问题
按最大价值/最小重量/最大单位重量价值先放背包的原则
活动选择问题
回溯法(通用解题法)
找出满足约束条件的所有解
在包含所有解的空间树中，按照深度优先策略，从根结点出发搜索解空间树
若结点肯定不包含解，跳过以该结点为根的子树，向其祖先结点回溯
若结点肯定包含，则进入继续按深度优先策略搜索
求问题任一解，只要搜索到问题就能结束，适合求组合数较大的问题
求问题的最优解，解空间至少包含问题的一个(最优)解
0/1背包问题
n皇后问题
分支限界法
找出满足约束条件的极大/极小解，即某种意义下的最优解
FIFO队列式(先进先出)
优先队列式
概率算法
数值概率算法
蒙特卡罗算法
拉斯维加斯算法
舍伍德算法
近似算法
放弃最优解，用近似解代替，简化/降低时间复杂度
穷举法
迭代法
递推法
递归法
算法有递归形式、非递归形式。递归式有展开法、代换法、递归树法、主方法。
排序问题
几种排序算法、索引及图的各种算法要了然于心，看见算法就知道用什么数据组织方式更高效，算法分析方法达到理解应用的水平(算法的分析过程及代码要非常清楚)
直接插入排序
冒泡排序
从数组最后开始, 两两比较元素, 顺序不对则交换元素
每一轮都冒一个泡到当前首元素位置, 减小数组长度进入下一轮
// 小到大的排序
public void test(int[] targetArr) {
int temp = 0; //临时变量
for (int i = 0; i < targetArr.length; i++) {
for (int j = i; j < targetArr.length; j++) {
if (targetArr[i] > targetArr[j]) {
//遇到小的就交换, 保证targetArr[i]是最小的
temp = targetArr[i];
targetArr[i] = targetArr[j];
targetArr[j] = temp;
}
}
}
}简单选择排序
希尔排序
快速排序
堆排序
基数排序
内部排序
外部排序
算法分析
时间复杂度
T(n)时间频度
算法花费的时间与算法中语句的执行次数成正比例
算法中的语句执行次数称为语句频度或时间频度。记为 T(n)=O(f(n))
f(n)同数量级
若有某个辅助函数f(n),使得n趋近无穷大，T（n)/f(n) 极限值不等于零，则f(n) T(n)同数量级
时间频度不同，但时间复杂度可能相同。
如：T(n)=n2+3n+4与T(n)=4n2+2n+1 它们的频度不同，但时间复杂度相同，都为O(n2)
O时间复杂度计算
算法的执行时间不随着问题规模n的增加而增长，即使有上千条语句，其执行时间是一个常数。
此时：T(n)= O(1)
有循环语句，时间复杂度由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的，例如：
x=1; for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++;
最内层语句是x++，其频度与问题规模n无直接关系，但与最外层i取值有关
最外层循环次数与问题规模n有关，此时：T(n)=O(n3/6+低次项)=O(n3)
算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关
i=n-1; while(i>=0&&(A[i]!=k)) i--; return i;
语句i--不仅与问题规模n有关，还与实例中k的取值有关
若A中没有与k相等元素，即 f(n)=n
若A的最后一个元素等于k，频度f(n)是常数0
空间复杂度
空间复杂度是指运行完一个程序所需内存的大小
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))
其中n为问题的规模，S(n)表示空间复杂度