1 算法优劣评价指标

时间复杂度（流程决定）

常数时间操作

• 如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间，称其为常数时间的操作。
• 常见的常数时间操作
• 常见的算术运算（+、-、*、/、% 等）
• 常见的位运算（>>、>>>、<<、|、&、^等）
• 赋值、比较、自增、自减操作等
• 数组寻址操作

如何确定算法流程的总操作数量与样本数量之间的表达式关系？

• 想象该算法流程所处理的数据状况，要按照最差情况来。
• 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
• 如果数据量为N，看看基本动作的数量和N是什么关系。

如何确定算法流程的时间复杂度？

当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。记为：O(忽略掉系数的最高阶项)

常见的时间复杂度排名

O(1)
O(logN)
O(N)
O(N*logN)
O(N^2) O(N^3) … O(N^K)
O(2^N) O(3^N) … O(K^N)
O(N!)

时间复杂度应用举例

• 选择排序
  • 过程：
    arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。
    arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。
    arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。
    …
    arr[N-1～N-1]范围上，找到最小值位置，然后把最小值交换到N-1位置。
  • 估算：
    很明显，如果arr长度为N，每一步常数操作的数量，如等差数列一般，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)。
    所以选择排序的时间复杂度为O(N^2)。

import java.util.Arrays;public class Code01_SelectionSort {public static void selectionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 0 ~ N-1// 1~n-1// 2for (int i = 0; i < arr.length - 1; i++) { // i ~ N-1// 最小值在哪个位置上  i～n-1int minIndex = i;for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 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;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {// Math.random()   [0,1)  // Math.random() * N  [0,N)// (int)(Math.random() * N)  [0, N-1]int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {// [-? , +?]arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// 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 testpublic 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 void main(String[] args) {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);selectionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);selectionSort(arr);printArray(arr);}}

• 冒泡排序
  • 过程：
    在arr[0～N-1]范围上：
    arr[0]和arr[1]，谁大谁来到1位置；arr[1]和arr[2]，谁大谁来到2位置…arr[N-2]和arr[N-1]，谁大谁来到N-1位置
    在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置
    在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置
    …
    最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置
  • 估算：
    很明显，如果arr长度为N，每一步常数操作的数量，依然如等差数列一般，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)。
    所以冒泡排序的时间复杂度为O(N^2)。

import java.util.Arrays;public class Code02_BubbleSort {public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 0 ~ N-1// 0 ~ N-2// 0 ~ N-3for (int e = arr.length - 1; e > 0; e--) { // 0 ~ efor (int i = 0; i < e; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);}}}}// 交换arr的i和j位置上的值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];}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// 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 testpublic 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 void main(String[] args) {		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);}}

• 插入排序
  • 过程：
    想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
    想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做。
    …
    想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
    最后一步，想让arr[0~N-1]上有序， arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
  • 该算法时间复杂度会因为数据状况的不同而不同。如果某个算法流程的复杂程度会根据数据状况的不同而不同，那么你必须要按照最差情况来估计。很明显，在最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般。
    所以，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)
    所以插入排序排序的时间复杂度为O(N^2)。

import java.util.Arrays;public class Code03_InsertionSort {public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 0~0 有序的// 0~i 想有序for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);}}}// i和j是一个位置的话，会出错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];}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {// Math.random() ->  [0,1) 所有的小数，等概率返回一个// Math.random() * N -> [0,N) 所有小数，等概率返回一个// (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机 for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// 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 testpublic 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 void main(String[] args) {int testTime = 500000;int maxSize = 100; // 随机数组的长度0～100int maxValue = 100;// 值：-100～100boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);insertionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {// 打印arr1// 打印arr2succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);insertionSort(arr);printArray(arr);}}

空间复杂度（流程决定）

作为输入参数的空间，不算额外空间。作为输出结果的空间，也不算额外空间。因为这些都是必要的、和现实目标有关的。所以都不算。但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。

常数项时间（实现细节决定）

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的。如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。

2 认识对数器

1. 实现你想要测的方法a。
2. 实现复杂度不好但是容易实现的方法b。
3. 实现一个随机样本产生器。
4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
5. 如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a和方法b。
6. 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

注：第一节中三种排序算法代码均已包含其对数器

3 认识二分法

有序不是所有问题求解时使用二分的必要条。只要能正确构建左右两侧的淘汰逻辑，就可以使用二分。

• 在一个有序数组中，找某个数是否存在

public class Code04_BSExist {public static boolean exist(int[] sortedArr, int num) {if (sortedArr == null || sortedArr.length == 0) {return false;}int L = 0;int R = sortedArr.length - 1;int mid = 0;// L..Rwhile (L < R) {// mid = (L+R) / 2;// L 10亿  R 18亿// mid = L + (R - L) / 2// N / 2    N >> 1mid = L + ((R - L) >> 1); // mid = (L + R) / 2if (sortedArr[mid] == num) {return true;} else if (sortedArr[mid] > num) {R = mid - 1;} else {L = mid + 1;}}return sortedArr[L] == num;}}

• 在一个有序数组中，找>=某个数最左侧的位置

import java.util.Arrays;public class Code05_BSNearLeft {// 在arr上，找满足>=value的最左位置public static int nearestIndex(int[] arr, int value) {int L = 0;int R = arr.length - 1;int index = -1; // 记录最左的对号while (L <= R) {int mid = L + ((R - L) >> 1);if (arr[mid] >= value) {index = mid;R = mid - 1;} else {L = mid + 1;}}return index;}// for testpublic static int test(int[] arr, int value) {for (int i = 0; i < arr.length; i++) {if (arr[i] >= value) {return i;}}return -1;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// 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();}public static void main(String[] args) {int testTime = 500000;int maxSize = 10;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxSize, maxValue);Arrays.sort(arr);int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());if (test(arr, value) != nearestIndex(arr, value)) {printArray(arr);System.out.println(value);System.out.println(test(arr, value));System.out.println(nearestIndex(arr, value));succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");}}

• 在一个有序数组中，找<=某个数最右侧的位置

import java.util.Arrays;public class Code05_BSNearRight {// 在arr上，找满足<=value的最右位置public static int nearestIndex(int[] arr, int value) {int L = 0;int R = arr.length - 1;int index = -1; // 记录最右的对号while (L <= R) {int mid = L + ((R - L) >> 1);if (arr[mid] <= value) {index = mid;L = mid + 1;} else {R = mid - 1;}}return index;}// for testpublic static int test(int[] arr, int value) {for (int i = arr.length - 1; i >= 0; i--) {if (arr[i] <= value) {return i;}}return -1;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// 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();}public static void main(String[] args) {int testTime = 500000;int maxSize = 10;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxSize, maxValue);Arrays.sort(arr);int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());if (test(arr, value) != nearestIndex(arr, value)) {printArray(arr);System.out.println(value);System.out.println(test(arr, value));System.out.println(nearestIndex(arr, value));succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");}}

• 局部最小值问题（找出一个局部最小值即可）

public class Code06_BSAwesome {public static int getLessIndex(int[] arr) {if (arr == null || arr.length == 0) {return -1; // no exist}if (arr.length == 1 || arr[0] < arr[1]) {return 0;}if (arr[arr.length - 1] < arr[arr.length - 2]) {return arr.length - 1;}int left = 1;int right = arr.length - 2;int mid = 0;while (left < right) {mid = (left + right) / 2;if (arr[mid] > arr[mid - 1]) {right = mid - 1;} else if (arr[mid] > arr[mid + 1]) {left = mid + 1;} else {return mid;}}return left;}}

4 认识异或运算性质

• 定义
  异或运算：相同为0，不同为1
  同或运算：相同以1，不同为0
  异或运算记成无进位相加！
• 性质
  • 0^N == N, N^N == 0
  • 异或运算满足交换律和结合律
• 例题
  • 如何不用额外变量交换两个数

a = a ^ b;
b = a ^ b;
a = a ^ b;

• 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

// arr中，只有一种数，出现奇数次public static void printOddTimesNum1(int[] arr) {int eor = 0;for (int i = 0; i < arr.length; i++) {eor ^= arr[i];}System.out.println(eor);}

• 怎么把一个int类型的数，提取出最右侧的1来

N & ((~N) + 1);

• 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数

// arr中，有两种数，出现奇数次public static void printOddTimesNum2(int[] arr) {int eor = 0;for (int i = 0; i < arr.length; i++) {eor ^= arr[i];}// eor = a ^ b// eor != 0// eor必然有一个位置上是1// 0110010000// 0000010000int rightOne = eor & (~eor + 1); // 提取出最右的1int onlyOne = 0; // eor'for (int i = 0 ; i < arr.length;i++) {//  arr[1] =  111100011110000// rightOne=  000000000010000if ((arr[i] & rightOne) != 0) {onlyOne ^= arr[i];}}System.out.println(onlyOne + " " + (eor ^ onlyOne));}

• 数出一个数的二进制形式中1的个数

public static int bit1counts(int N) {int count = 0;//   011011010000//   000000010000     1//   011011000000while(N != 0) {int rightOne = N & ((~N) + 1);count++;N ^= rightOne;// N -= rightOne}return count;	}