算法初级-01-时间复杂度
2019-07-03 本文已影响0人
囧么肥事
年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
算法时间复杂度评定标准
实例1：一个简单的理解时间复杂度的例子
实例2：冒泡排序
实例3：选择排序
实例4：插入排序
实例5：对数器
实例6：理解递归行为，以及递归行为事件复杂度的估算
实例7：归并排序
实例8：小和问题和逆序对问题
算法的评定标准有两个-时间复杂度，空间复杂度
1、常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。+
例如：
- 加减乘除
- 位运算
- 数组寻址
这些操作的时间和样本是数据量是没有关系的
时间复杂度是一个算法流程中，评价常数操作数量的指标。
常用O（读作big O）来表示，具体，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N), 那么时间复杂度为O(f(N))。
评价算法流程好坏
评价一个算法流程的好坏，先看时间复杂度的指标，然后在分析不同数据样本下的实际运行时间，也就是常数项时间。
如：第一种算法流程的时间复杂度指标为N，所以他的算法好一些。（当然数据样本非常小，第二种好一些）
1562051795592.png
实例·1
一个简单的理解时间复杂度的例子
一个有序数组A，另一个无序数组B，请打印B中的所有不在A中的数，A数 组长度为N，B数组长度为M。
可以使用三种常用的算法流程来解决这个问题：
算法流程1：对于数组B中的每一个数，都在A中通过遍历的方式找一下；
算法流程2：对于数组B中的每一个数，都在A中通过二分的方式找一下；
算法流程3：先把数组B排序，然后用类似外排的方式打印所有不在A中出现 的数；
三个流程，三种时间复杂度的表达...
如何分析好坏？
流程1
时间复杂度：O(N*M)
流程2
二分法：每次排除一半的样本数据
时间复杂度：O(M*logN)
ps : logN是以2为底
流程3
先排序 O(M*logM)
外排比较时间复杂度：O(N + M)
总结，流程1性能最差；如果A长，B短，流程2好；如果A短，B长，流程3好；
实例2
冒泡排序
每次相邻的两个数进行比较，然后交换（需要时交换），每一趟都找到了当前样本中的最大数
// 排序
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
// 每一趟少一个最大元素，固定范围
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) { // i 不能= end ，不然 i + 1 数组越界
if (arr[i] > arr[i + 1])
swap(arr, i, i + 1);
}
}
// 打印结果
System.out.println(Arrays.toString(arr));
}
// 交换
public static void swap(int[] arr, int i, int j) {
// 交换时间复杂度：常数时间复杂度
// 交换只涉及到了数组元素的寻址操作，这是常数时间操作
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
时间复杂度O(N^2)，额外空间复杂度O(1)
实例3
选择排序
每次选择一个最小的放在该放的位置上
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
/*
5 9 4 1 2
第一次 i = 0, 循环完毕找到 数1 的下标，交换数，将1 放到 第0 个位置上
交换后结果：1 9 4 5 2
第二次 i = 1, 循环完毕找到 数2 的下标，交换数，将2 放到 第1 个位置上
交换后结果：1 2 4 5 9
依次类推 ...5 个数，需要循环4次
*/
// 外层规定循环范围, 每次找到最小的数，放在第 i 个位置上
// N个元素，当前N-1 个位置上的数已经确定，则最后一个也是确定的，所以 i < arr.length - 1
for (int i = 0; i < arr.length - 1; i++) {
// 假设当前 i 位置上的数就是最小数
int minIndex = i;
// 内层寻找最小数下标
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[minIndex] < arr[j] ? minIndex : j;
}
swap(arr, i, minIndex);
}
System.out.println(Arrays.toString(arr));
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
时间复杂度O(N^2)，额外空间复杂度O(1)
实例4
插入排序
算法时间复杂度
插入排序和选择排序，冒泡排序不同，它跟数据的状态有关。
最好情况：数据是有序的如：1 2 3 4 5，O(N)
最坏情况：数据是反序的如：5 4 3 2 1, 求小到大序，则O(N^2)
时间复杂度O(N^2)，额外空间复杂度O(1)
将数据组划分为两块，一块是已经排序好的，一块是待排序的
每一次从待排序数组中取出一个元素，进行插入
插入选择：从排序好的数组的最后一个元素开始进行倒序遍历，寻找它应该存放的位置，进行交换插入
实例5
对数器
采用对数器来进行验证
1、一个你想要测试的方法 a
2、一个绝对正确但是复杂度不好是方法 b
3、实现一个随机样本产生器
4、实现对比的方法
5、把方法a和方法b比对很多次来验证方法a 是否正确
6、如果有一个样本使得对比出错，打印出样本，分析到底是哪个方法出错
7、当样本数量很多时比对测试依然正确，可以确定方法a 正确
测试一下插入排序
模型
import java.util.Arrays;
/**
* @description: 排序随机样本产生器模型
* @version: 1.0
*/
public class SortModel {
// for test : 一个绝对正确的排序方法 --> 这里使用Java自带方法
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test : 随机样本产生器
public static int[] generateRandomArray(int maxSize, int maxValue) {
// 随机数组长度，随机长度
int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
// 随机数据
for (int i = 0; i < arr.length; i++) {
// 两个随机数相减，可以随机出负数
arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
}
return arr;
}
// for test : 复制数组
public static int[] copyArray(int[] arr) {
if (arr == null)
return null;
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++)
res[i] = arr[i];
return res;
}
// for test : 实现一个对比方法
public static boolean isEqual(int[] arr1, int[] arr2) {
// 有一个数组为null
if (arr1 == null && arr2 != null
|| arr1 != null && arr2 == null)
return false;
// 两个数组都为null
if (arr1 == null && arr2 == null) return true;
// 两个数组的长度不一致
if (arr1.length != arr2.length) return false;
// 对比两个数组中的每一个元素
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i])
return false;
}
return true;
}
/*
采用对数器来进行验证
1、一个你想要测试的方法 a
2、一个绝对正确但是复杂度不好是方法 b
3、实现一个随机样本产生器
4、实现对比的方法
5、把方法a和方法b比对很多次来验证方法a 是否正确
6、如果有一个样本使得对比出错，打印出样本，分析到底是哪个方法出错
7、当样本数量很多时比对测试依然正确，可以确定方法a 正确
*/
}
测试
import cn.zqtao.learn.model.SortModel;
import java.util.Arrays;
/**
* @description: 插入排序（相对工程中使用挺多）
* <p>
* 类似插牌
* <p>
* 将数据组划分为两块，一块是已经排序好的，一块是待排序的
* <p>
* 每一次从待排序数组中取出一个元素，进行插入
* 插入选择：从排序好的数组的最后一个元素开始进行倒序遍历，寻找它应该存放的位置，进行交换插入
* @version: 1.0
*/
public class Code_02_InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
// 外层循环控制循环次数, 默认认为第一个元素是已经排序好的
for (int i = 1; i < arr.length; i++) {
// 对已经排序好的数组进行倒叙遍历，查询新元素的插入下标
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
// 不需要使用临时变量，进行交换
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
int testTime = 5000;
int maxSize = 10;
int maxValue = 100;
for (int i = 0; i < testTime; i++) {
int[] randomArr = SortModel.generateRandomArray(maxSize, maxValue);
int[] arr1 = SortModel.copyArray(randomArr);
int[] arr2 = SortModel.copyArray(randomArr);
insertionSort(arr1);
SortModel.comparator(arr2);
if (!SortModel.isEqual(arr1, arr2)) {
System.out.println("错误: " + Arrays.toString(randomArr));
System.out.println("待测方法结果：" + Arrays.toString(arr1));
System.out.println("正确方法结果：" + Arrays.toString(arr2));
break;
}
}
}
}
实例6
理解递归行为，以及递归行为事件复杂度的估算
master公式的使用
T(N) = aT(N/b) + O(N^d)* 满足master此形式的，都可以使用下面的计算方法计算时间复杂度
-
log(b,a) > d ---> 复杂度为O(N^log(b,a))
-
log(b,a) = d ---> 复杂度为O(N^d * logN)
-
log(b,a) < d ---> 复杂度为O(N^d)
ps: log(b, a) 表示以b 为底
补充阅读：www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html
实例7
归并排序
分治思想
左边部分排序为有序
右半部分排序为有序
采用外排方式，合并两个有序部分到一个临时数组
复制回写到原数组
import cn.zqtao.learn.model.SortModel;
import java.util.Arrays;
/**
* @description: 归并排序
* <p>
* 分治思想
* <p>
* 左半部分排序
* 右半部分排序
* <p>
* 采用外排方式，合并两个有序部分到一个临时数组
* <p>
* 复制回原数组
* @version: 1.0
*/
public class Code_03_MergerSort {
public static void mergerSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
sortProcess(arr, 0, arr.length - 1);
// System.out.println(Arrays.toString(arr));
}
public static void sortProcess(int[] arr, int L, int R) {
if (L == R)
return;
int mid = L + ((R - L) >> 1); // 等同于 (L + R) / 2
sortProcess(arr, L, mid);
sortProcess(arr, mid + 1, R);
merger(arr, L, mid, R); // O(N)
// T(N) = 2 T(N/2) + O(N) 符合master公式
// 所以时间复杂度： O(N * logN)
// 空间复杂度：O(N) 临时辅助数组
}
// 合并两个有序部分
private static void merger(int[] arr, int L, int mid, int R) {
// 辅助数组
int[] help = new int[R - L + 1];
int i = 0;
// 双指针，分别指向第一个有序部分第一个数位置，第二个有序部分第一个数位置
int p1 = L;
int p2 = mid + 1;
// 外排方式选填进入临时辅助数组的数, 当两个指针任意一个越界时跳出
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 有且只有一个越界
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
// 回写到原数组
for (int j = 0; j < help.length; j++) {
arr[L + j] = help[j];
}
}
public static void main(String[] args) {
int testTime = 5000;
int maxSize = 10;
int maxValue = 100;
for (int i = 0; i < testTime; i++) {
int[] randomArr = SortModel.generateRandomArray(maxSize, maxValue);
int[] arr1 = SortModel.copyArray(randomArr);
int[] arr2 = SortModel.copyArray(randomArr);
mergerSort(arr1);
SortModel.comparator(arr2);
if (!SortModel.isEqual(arr1, arr2)) {
System.out.println("错误: " + Arrays.toString(randomArr));
System.out.println("待测方法结果：" + Arrays.toString(arr1));
System.out.println("正确方法结果：" + Arrays.toString(arr2));
break;
}
}
}
}
时间复杂度： O(N * logN)
空间复杂度：O(N) 临时辅助数组
实例8
小和问题和逆序对问题
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和。
例子： [1,3,4,2,5] 1左边比1小的数，没有； 3左边比3小的数，1； 4左边比4小的数，1、3； 2左边比2小的数，1； 5左边比5小的数，1、3、4、2； 所以小和为1+1+3+1+1+3+4+2=16
逆序对问题 在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序 对。
小和问题
import cn.zqtao.learn.model.SortModel;
import java.util.Arrays;
/**
* @description: 小和问题
* <p>
* 小和问题
* 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和。
* 例子：
* [1,3,4,2,5]
* 1左边比1小的数，没有；
* 3左边比3小的数，1；
* 4左边比4小的数，1、3；
* 2左边比2小的数，1；
* 5左边比5小的数，1、3、4、2；
* 所以小和为1+1+3+1+1+3+4+2=16
* @version: 1.0
*/
public class Code_04_SmallSum {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) return 0;
return mergesort(arr, 0, arr.length - 1);
}
public static int mergesort(int[] arr, int L, int R) {
if (L == R) return 0;
int mid = L + ((R - L) >> 1);
return mergesort(arr, L, mid) +
mergesort(arr, mid + 1, R) +
merge(arr, L, mid, R);
//左边产生的小和+右边产生的小和+合并产生的小和就是整个数组的小和
}
public static int merge(int[] arr, int L, int mid, int R) {
// 辅助数组
int[] help = new int[R - L + 1];
int i = 0;
// 双指针
int p1 = L;
int p2 = mid + 1;
int res = 0;
while (p1 <= mid && p2 <= R) {
// 左边小于右边，左边数 * 右边比左边大的数的个数，因为已经使用归并排序进行了排序
// 所以右边剩下的数也比左边数大
// 如左边 1 3
// 右边 2 5 6
// 1 < 2 ,此时右边数，5 6 一定都比1大， 则 小和结果是 1 * 3
res = arr[p1] < arr[p2] ? arr[p1] * (R - p2 + 1) : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
return res;
}
// for test 写一个实现简单，绝对正确但是时间复杂度高的算法
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] randomArr = SortModel.generateRandomArray(maxSize, maxValue);
int[] arr1 = SortModel.copyArray(randomArr);
int[] arr2 = SortModel.copyArray(randomArr);
if (!SortModel.isEqual(arr1, arr2)) {
succeed = false;
System.out.println("错误: " + Arrays.toString(randomArr));
System.out.println("待测方法结果：" + Arrays.toString(arr1));
System.out.println("正确方法结果：" + Arrays.toString(arr2));
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
逆序对
import java.util.Arrays;
import java.util.Scanner;
/**
* @description: 逆序对问题
* 在一个数组中，左边的数如果比右边的数大，则两个数构成一个逆序对，请打印所有逆序对
* @version: 1.0
*/
public class Code_05_InvertedNum {
public static void invertedNum(int[] arr) {
if (arr == null || arr.length < 2) return;
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int L, int R) {
if (L == R) return;
int mid = L + ((R - L) >> 1);
// 打印左边逆序对
mergeSort(arr, L, mid);
// 打印右边逆序对
mergeSort(arr, mid + 1, R);
// 打印合并后的逆序对
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int mid, int R) {
// 辅助数组
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
if (arr[p1] > arr[p2]) {
for (int j = p2; j <= R; j++) {
System.out.println("逆序对：" + arr[p1] + "--" + arr[j]);
}
}
help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] str = sc.nextLine().split(",");
int[] num = new int[str.length];
for (int i = 0; i < str.length; i++) {
num[i] = Integer.parseInt(str[i]);
}
invertedNum(num);
}
sc.close();
}
}
以上都是算法课程学习总结
