时间复杂度
二进制
二进制操作
二分查找
冒泡排序
快速排序
动态规划
例子一：切钢条
例子二：过河问题
例子三：最长公共子序列
例子四：最长公共连续子序列
例子五：01背包问题
时间复杂度
一个算法在给定输入下执行的基本操作数或步数，我们假定执行每行代码需要的时间为常量
二进制
二进制原码、反码、补码：
- 二进制的最高位是符号位：0表示正数，1表示负数
- 正数的原码、反码、补码都一样
- 负数的反码 = 它的原码符号位不变，其他位取反
- 负数的补码 = 它的反码 +1
- 0的反码、补码都是0
- 补码的补码是原码
如
- 2的原码：00000000 00000000 00000000 00000010
- -2的原码：10000000 00000000 00000000 00000010
- -2的反码：11111111 11111111 11111111 11111101
- -2的补码：11111111 11111111 11111111 11111110
查看数字的二进制表示，可以用Integer.toBinaryString(-1)
十六进制其实是补码表示，0xFFFFFFFF等于十进制-1
二进制操作
"&"与
"|"或
"^"异或：不相同才为1
">>"右移：正数左边补0，负数左边补1
"<<"左移：右边补0
二分查找
描述：在有序数组里查找一个值，查找成功返回下标，否则返回-1
思路：
- 用数组中间的值，与给定值比较，相等则查找成功
- 不相等，把数组分为两半，在其中一半中继续步骤1
- 直到查找成功，或子数组不存在
时间复杂度：
第一步耗时O(1)，一个长度为n的数组，一共要进行1 + logn次第一步，因此时间复杂度是O(logn)
private static int binarySearch(int[] arr, int key) {
if (arr == null || arr.length <= 0) {
return -1;
}
int start = 0;
int end = arr.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2; // 防止溢出
if (arr[mid] == key) {
return mid;
}else if (arr[mid] > key) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return -1;
}
冒泡排序
思路：
- 针对无序序列，两两比较，顺序不对则交换，一趟排序后序列末尾的值是有序的
- 重复步骤1，直到无序序列为空
private static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int end = arr.length - 1;
int tem;
for (int i = end - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
if (arr[j] > arr[j+1]) {
tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
}
}
}
}
时间复杂度：
上述算法，无论输入如何，时间复杂度都是O(N^2)
冒泡排序改进：
上述代码，如果内层循环中没有进行数据交换，那么内层循环中的值已经是有序的了，此时可以跳出循环
private static void bubbleSort1(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int end = arr.length - 1;
int tem;
boolean swapped;
for (int i = end - 1; i >= 0; i--) {
swapped = false;
for (int j = 0; j <= i; j++) {
if (arr[j] > arr[j+1]) {
tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
swapped = true;
}
}
if (!swapped)
break;
}
}
时间复杂度：
此时如果输入已经是正序的，那么外层循环只执行一次，此时时间复杂度O(n)
因此对冒泡排序改进来说，最好的时间复杂度是O(n)
快速排序
思路：
- 选取一个主元，进行一次定位，定位后，主元左边元素都比它小，主元右边元素都比它大
- 针对左右两个分区，分别执行步骤1
// 定位
private static int position(int[] arr, int start, int end) {
int i = start;
int j = end;
int key = arr[i];
while (i < j) {
while(i < j && arr[j] > key) { // 由于可能出现i==j，因此每一步都加i<j判断，防止ij乱加减
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] <= key) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
} // 最后i==j
arr[i] = key; // 由于是覆盖，而不是交换，因此最后要有一步赋值
return i;
}
// 快速排序
private static void quickSort(int[] arr, int start, int end) {
if (arr == null || arr.length <= 1 || start >= end || start < 0 || end > arr.length) {
return;
}
int pos = position(arr, start, end);
quickSort(arr, pos+1, end);
quickSort(arr, start, pos-1);
}
快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用另的方法排序以减小递归深度。也可以选中间的数作为基准数，要实现这个方便非常方便，直接将中间的数和第一个数进行交换就可以了（我们用的是覆盖，因此这里是用第一个数覆盖中间的数）
int key = arr[i];
替换为
int mid = start + (end - start) / 2;
int key = arr[mid];
arr[mid] = arr[i];
时间复杂度：
最好场景：T(n) = 2T(n / 2) + n，最好时间复杂度O(nlogn)
最坏场景：T(n) = T(n - 1) + n，最坏时间复杂度O(n^2)
动态规划
动态规划和分治算法相似，都是通过组合子问题的解来求解原问题。
特殊情况下，分治算法会反复求解子问题
动态规划每个子问题只求解一次，将其保存起来，避免不必要的计算
动态规划通常用来求解最优化问题。
动态规划有下面两种方式，我们通常使用第二种
- 带备忘的自顶向下法：通常用一个数组保存已经计算过的值，求解时，如果数组中有值，直接返回，否则才进行计算。（计算f(n)，在计算f(n)的过程中去计算f(n-1)...）
- 自底向上法：求解一个问题时，直至它依赖的所有子问题均已求解完成，才求解它。（先计算f(0)，在计算f(1)...直到f(n)）
例子一：切钢条
问题描述：长度为i的钢条，价格为p(i)，i是整数。给定一段长度为n的钢条，怎么切能让收益最大？
思路：
- 长度为n的钢条，最大切割收益用f(n)表示。
- f(n)怎么计算呢，考虑钢条n所有可能的切割方案，先想第一步，第一刀切在哪，第一刀可以切长度为1，2，3，...，n（这是所有可能的场景），那么第一刀切长度i的收益是p(i)+f(n-i)
- 最大切割收益f(n)，即所有可能场景的最大值，于是f(n) = max(p(i)+f(n-i)), i=1 to n
直接递归法
private static int cut(int[] price, int n) {
if (n == 0) {
return 0;
}
int res = -1;
for (int i = 1; i <= n; i++) {
System.out.println(n + "-" + (n-i));
res = Math.max(res, price[i-1] + cut(price, n-i));
}
return res;
}
动态规划-带备忘自顶向下法
private static int cut1(int[] price, int n) {
int[] fArr = new int[n+1];
for (int i = 0; i < n+1; i++) {
fArr[i] = -1;
}
return cut1_aug(price, n, fArr);
}
private static int cut1_aug(int[] price, int n, int[] fArr) {
if(fArr[n] >= 0) {
return fArr[n];
}
int res = -1;
if (n == 0) {
res = 0;
}else {
for (int i = 1; i <= n; i++) {
System.out.println(n + "-" + (n-i));
res = Math.max(res, price[i-1] + cut1_aug(price, n-i, fArr));
}
}
fArr[n] = res;
return res;
}
动态规划-自底向上法
private static int cut2(int[] price, int n) {
int[] f = new int[n+1]; // 最优解数组
for (int i = 1; i <= n; i++) {
int res = -1;
for (int j = 1; j <= i; j++) {
System.out.println("*");
res = Math.max(res, price[j-1] + f[i-j]);
}
f[i] = res;
}
return f[n];
}
例子二：过河问题
一座桥，n个人，一个手电筒。桥一次最多通过两个人，两个人过桥时间为两人中时间较长者，过桥必须用手电筒，所以每次过桥之后需要有人把手电筒送回来，问n个人过桥总时间最短是多少？
http://www.360doc.com/content/08/0706/02/37063_1402145.shtml
A ---> B
最佳场景：
1.每次B->A送手电筒的人，一定是B当中最快的
2.手电筒在A时，速度最快的人一定在A
3.每次A->B的两人，要么这两人其中一个是所有人中最快的，要么这两个人到B之后再也不回来
4.每次B->A送手电筒的人，一定是所有人中最快的，或者次快的
n个人中：
-最快的人，单人过桥时间设为a
-次快的人，单人过桥时间设为b
-次慢的人，单人过桥时间设为y
-最慢的人，单人过桥时间设为z
那么，最慢和次慢的人过桥有两种模式
模式一：（耗时y+a+z+a）
- ay过桥
- a回来
- az过桥
- a回来
模式二：（耗时b+a+z+b）
- ab过桥
- a回来
- yz过桥
- b回来
另一种思路，同样按过河时间从小到大排序
- 1个人：a直接过
- 2个人：ab直接过
- 3个人：ab-a-ac
- 4个人：和上面的模式相同
场景一：ab-a-ac-a-ad，耗时b+a+c+a+d
场景二：ab-a-cd-b-ab，耗时b+a+d+b+b - n个人
因为一次最多过两个人，所以考虑最后升两个人（耗时最长），这两个人的过河方式有2种，对应上面两种模式
模式一：f(n) = f(n-2) + a + c + a + d
模式二：f(n) = f(n-2) + a + d + b + b
第i个人过河时间为a[i]，递增
于是 f(n) = min{f(n-2)+arr[1]+arr[n-1]+arr[1]+arr[n], f(n-2)+arr[1]+arr[n]+arr[2]+arr[2]}
/**
* 过河时间
* 输入：每个人单独过河时间，从小到大排列
* 输出：所有人过河最短时间
*/
private static int leastTime(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
int i = arr.length - 1;
int sum = 0;
for (; i > 2; i -= 2) {
int t1 = 2 * arr[0] + arr[i-1] + arr[i];
int t2 = 2 * arr[1] + arr[0] + arr[i];
sum += Math.min(t1, t2);
}
if (i == 2) { // 剩下3人
sum = sum + arr[0] + arr[1] + arr[2];
}
if (i == 1) { // 剩下2人
sum = sum + arr[1];
}
return sum;
}
例子三：最长公共子序列LCS
描述：给定两个序列X、Y，如果Z即是X的子序列，又是Y的子序列，那么称Z是X和Y的公共子序列
比如：X=abcbdab，Y=bdcaba，那么bcba是X和Y的一个最长公共子序列
思路：
我们设X={x1,x2...xm}，Y={y1,y2...yn}两个序列，Z={z1,z2...zk}是X和Y的任意一个LCS，那么
1.如果xm = yn，那么zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS
2.如果xm != yn，那么zk != xm表示Z是Xm-1和Y的一个LCS
3.如果xm != yn，那么zk != yn表示Z是X和Yn-1的一个LCS
于是
用c[i,j]表示Xi和Yj的LCS长度，可以得到下面的公式
// 最长公共子序列
private static int lcsLenth(char[] x, char[] y) {
if (x.length == 0 || y.length == 0) {
return 0;
}
int m = x.length;
int n = y.length;
int[][] res = new int[m+1][n+1]; // 动态规划典型用法，字典
for (int i = 1; i <= m; i++) {
for (int j = 1; j<= n; j++) {
if (x[i-1] == y[j-1]) {
res[i][j] = res[i-1][j-1] + 1;
}else if (res[i-1][j] > res[i][j-1]) {
res[i][j] = res[i-1][j];
}else {
res[i][j] = res[i][j-1];
}
}
}
return res[m][n];
}
例子四：最长公共子串
https://blog.csdn.net/u010397369/article/details/38979077
描述：给定两个字符串X和Y，求最长公共子串，注意子串是连续了（上面说的子序列可以不连续）
思路：和求最长公共子序列相同的思路
我们定义S(i,j)表示“以xi和yj结尾的最长公共子串”，用c[i,j]表示其长度
那么
// 最长公共子串
private static int lcsLenth2(char[] x, char[] y) {
if (x.length == 0 || y.length == 0) {
return 0;
}
int m = x.length;
int n = y.length;
int[][] res = new int[m+1][n+1];
int max = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[i-1] == y[j-1]) {
res[i][j] = res[i-1][j-1] + 1;
if (res[i][j] > max) {
max = res[i][j];
}
}
}
}
return max;
}
上述方法需要一个mn的数组，空间复杂度可以优化到O(1)
上述方法实际是计算了下面这个数组
我们可以遍历每一条对角线，求出最大值，这样只需要O(1)的空间
// 最长公共子串
private static int lcsLenth3(char[] x, char[] y) {
if (x.length == 0 || y.length == 0) {
return 0;
}
int i = x.length + y.length - 1;
int tem = 0; // 代替上面二维数组的临时变量
int max = 0;
while (i > 0) { // 从矩形右上角，沿上边和左边，遍历到左下角
int col = i > y.length ? (i-y.length) : 0; // 对角线起点 列
int row = i > y.length ? 0 : (y.length - i); // 对角线起点 行
while (col < x.length && row < y.length) {
if (x[col] == y[row]) {
tem++;
max = tem > max ? tem : max;
}else {
tem = 0;
}
col++;
row++;
}
i--;
}
return max;
}
例子五：01背包问题
描述：有N件物品和一个容量为V的背包。第i件物品的容量是c(i)，价值是v(i)。每种物品仅有一件，可以选择放或不放。求解将哪些物品装入背包可使价值总和最大。
思路：
f[i][j] = max{f[i-1][j], f[i-1][j-c(i)] + v(i)}
f[i][j]表示：“将前i件物品放入容量为j的背包中”的最大价值
考虑第i件物品，
1.背包单独放不下，即j<c(i)
-- 此时f[i][j]=f(i-1,j)
2.背包单独放的下，即j>=c(i)
-- 放，此时最大价值是，把前i-1个物品放入容量为j-c(i)的背包的最大价值，加上物品i的价值
-- 不放，此时最大价值是，把前i-1个物品放入容量为v的背包，f[i-1][j]
f[i][j] = max{f[i-1][j], f[i-1][j-c(i)] + v(i)}
// 01背包
private static int maxV(int[] c, int[] v, int pac) {
if (c.length == 0 || v.length == 0 || c.length != v.length) {
return -0;
}
int num = c.length; // 物品个数
int[][] maxV = new int[num+1][pac+1]; // 行号：物品号 列号：容量大小
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= pac; j++) {
if (j < c[i-1]) {
maxV[i][j] = maxV[i-1][j];
}else if (maxV[i-1][j] > maxV[i-1][j-c[i-1]] + v[i-1]) {
maxV[i][j] = maxV[i-1][j];
}else {
maxV[i][j] = maxV[i-1][j-c[i-1]] + v[i-1];
}
}
}
return maxV[num][pac];
}
public static void main(String[] args) {
int[] c = {4,5,6,2,2}; // 物品占用
int[] v = {6,4,5,3,6}; // 物品价值
maxV(c, v, 10);
}
