本文共 5000 字，大约阅读时间需要 16 分钟。
常数时间的操作：一个操作如果和数据量没有关系，每次都是 固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的指标。常用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中出现 的数； 三个流程，三种时间复杂度的表达... 如何分析好坏？
对于算法流程1来讲，其时间复杂度为O(M*N)
对于算法流程2来说，二分查找(有序数组)时间复杂度O(log2N)，每次过滤掉一半的数，其时间复杂度为O(logN)，其中logN默认以2为底，所以最终算法2的时间复杂度为O(M*logN)
对于算法流程3来说，假设A，B数组都已经有序，假设A数组元素为1,2,4,6,7，而B数组排序后元素为3,6,9，则当a指针打向1位置，思路如下图：
谁小移动谁，当b<=a，则移动b
1）排序的时间复杂度可以做到 O(M*logM)
2）类似外排的方式检查，由上述分析结果可知，时间复杂度为O(N+M)
所以，算法流程3的时间复杂度为 O(M*logM)+O(N+M)
冒泡排序
冒泡排序细节的讲解与复杂度分析 时间复杂度O(N^2)，额外空间复杂度O(1)
举例：比如数组 3,2,4,0,7
1）先看0位置和1位置，如果0位置比1位置大，俩个数交换，原数组变为2,3,4,0,7
2）看1位置和2位置，如果1位置比2位置大，俩个数交换，否则不交换，步骤1的数组变为 2,3,4,0,7
3）看2位置和3位置，如果2位置比3位置大，俩个数交换，步骤2的数组变为2,3,0,4,7
4）看3位置和4位置，如果3位置比4位置大，俩个数交换，否则不交换，步骤3的数组变为2,3,0,4,7
。。。。。
即每次都是0和1比较，1和2比较，2和3比较。。。，如此遍历，最大的数在最后一个位置。此时，排好一个数。
如此循环。。。具体代码如下：
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); } } }}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];} 因此，冒泡排序时间复杂度是等差数列之和，即O(N^2)
0------end
0------end-1
0-------end-2
。。。。。
选择排序
思路：一个数组进行排序。
1）在0到n-1位置上，进行查找最小值，和0位置进行交换。（时间复杂度n）
2）在1到n-1位置上，进行查找最小值，放在1位置上（和1位置进行交换）。（时间复杂度n-1）
3）在2到n-1位置上，进行查找最小值，放到2位置上。（时间复杂度n-2）
。。。。。。
直到所有元素排好顺序，总的时间复杂度为等差数列之和，为O(N^2),具体代码如下：
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); }}public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;}
插入排序
假如有数组：5,3,4,0,6对应数组角标0,1,2,3,4
1）首先0位置不动,得到5,)3,4,0,6
2）1位置和0位置比较，如果1位置比0小，则0和1交互得到3,5,) 4,0,6 ------此时，0到1位置已经排好顺序
3）2位置和1位置上的数比较，如果2位置比1小，就交换，得到3,4,5,0,6,即4来到了角标1的位置，再和角标0位置比较，如果小，就交换，此时不用交换，则0-2上的数排好顺序3,4,5,) 0,6
3）角标为3的数和角标为2上的数进行比较，步骤同上，得到0,3,4,5,) 6,此时，0到3位置排好顺序。
4）角标为4的数和角标为3上的数进行比较，步骤同上，得到0,3,4,5, 6
具体代码如下：
public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { //j=i-1，则j+1=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];} 插入排序的复杂度
1）最好情况，如果数组已经排好序，时间复杂度O(N)
2）平均情况
3）最差情况,如果数组逆序，每一次都要交换，时间复杂度O(N^2)
对数器的运用
对数器的概念和使用
0，有一个你想要测的方法a，
1，实现一个绝对正确但是复杂度不好的方法b，
2，实现一个随机样本产生器
3，实现比对的方法
4，把方法a和方法b比对很多次来验证方法a是否正确。
5，如果有一个样本使得比对出错，打印样本分析是哪个方法出 错
6，当样本数量很多时比对测试依然正确，可以确定方法a已经 正确。
一，检测冒泡排序
// for test 步骤1：准备一个绝对正确的方法public static void comparator(int[] arr) { Arrays.sort(arr);} // for test 步骤2：产生随机样本的产生器public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { //随机产生元素，该元素可能为正，可能为负，可能为0 arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr;} // for test 步骤3：实现对比方法public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } 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;} // for testpublic static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println();} // for testpublic 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 void main(String[] args) { //测试50万次 int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); bubbleSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); bubbleSort(arr); printArray(arr);} 转载地址：http://cnuwi.baihongyu.com/