虽然以前学过，再次回顾还是有别样的收获~ 认识时间复杂度 常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。 时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N)，那么时间复杂度为O(f(N))。 评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间。 例子一 一个简单的理解时间复杂度的例子 一个有序数组A，另一个无序数组B，请打印B中的所有不在A中的数，A数组长度为N，B数组长度为M。 算法流程1：对于数组B中的每一个数，都在A中通过遍历的方式找一下； 算法流程2：对于数组B中的每一个数，都在A中通过二分的方式找一下； 算法流程3：先把数组B排序，然后用类似外排的方式打印所有在A中出现的数； 三个流程，三种时间复杂度的表达... 如何分析好坏？ 例子二 对数器的概念和使用 0，有一个你想要测的方法a， 1，实现一个绝对正确但是复杂度不好的方法b， 2，实现一个随机样本产生器 3，实现比对的方法 4，把方法a和方法b比对很多次来验证方法a是否正确。 5，如果有一个样本使得比对出错，打印样本分析是哪个方法出错 6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。 对数器的例子 例子三 冒泡排序细节的讲解与复杂度分析 时间复杂度O(N^2)，额外空间复杂度O(1) 复制代码 public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } } } 复制代码 例子四 选择排序的细节讲解与复杂度分析 时间复杂度O(N^2)，额外空间复杂度O(1) 复制代码 public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } } 复制代码 例子五 插入排序（类似整理扑克牌）的细节讲解与复杂度分析 时间复杂度O(N^2)，额外空间复杂度O(1) 复制代码 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); } } } 复制代码 例子六 剖析递归行为和递归行为时间复杂度的估算 一个递归行为的例子 master公式的使用 T(N) = a*T(N/b) + O(N^d) [a是过程发生次数，N/b是子问题，O(N^d)剩下的时间复杂度] 1) log(b,a) > d -> 复杂度为O(N^log(b,a)) 2) log(b,a) = d -> 复杂度为O(N^d * logN) 3) log(b,a) < d -> 复杂度为O(N^d) 补充阅读：www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html 例子七 归并排序的细节讲解与复杂度分析 时间复杂度O(N*logN)，额外空间复杂度O(N) 复制代码 public static void mergeSort(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 m, int r) { int[] help = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while (p1 <= m && p2 <= r) { help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[l + i] = help[i]; } } 复制代码 例子八 小和问题和逆序对问题 小和问题 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。 例子： [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 逆序对问题 在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。 答案 作者： kent鹏 出处： http://www.cnblogs.com/xieyupeng/ 关于作者：专注JAVAEE领域，请多多赐教！ 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。 分类: 数据结构与算法https://www.cnblogs.com/xieyupeng/p/9915699.html