认识时间复杂度
常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
常数时间的操作符合两点：
- 一次操作的时间与数量级没有关系。
- 每次操作花费的时间是确定有限的。
时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作bigO）来表示。具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果记为f(N)，那么时间复杂度为O(f(N))。
如果一个算法的时间复杂度是 a*N^2 + b*N + c，那么 a*N^2 就是高阶项，b*N为低阶项，c为常数项。不要低阶项就是抛除 b*N + c ，只留下最高阶 a*N^2；也不要高阶项的系数就是抛除系数a，最后的结果为 N^2，所以这个算法的时间复杂度为 O(N^2)。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是常数项时间。
常用的时间复杂度按照耗费的时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
对数器的概念和使用
对数器是用来测试代码正确性的，我们在找不到合适的oj系统测试自己的代码时，可以自己写一个对数器对代码进行测试。
1，有一个你想要测的方法A
比如我写了一个排序算法A，需要检测是否正确。
public static void bubbleSort(int[] arr){
if(arr == null || arr.length == 0){
return;
}
for(int end = arr.length - 1; end > 0; end--){
for(int i = 0; i < end; i++){
if(arr[i] > arr[i + 1]){
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
2，实现一个绝对正确但是复杂度不好的方法B
这里使用系统的排序算法保证算法的正确性。
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
3，实现一个随机样本产生器
这个方法产生一个最大长度maxSize和最大值maxValue的随机数组，作为一次随机样本。
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++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
4，实现比对的方法
对比我需要检测的方法A和绝对正确的方法B所产生的结果是否相同。
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;
}
5，把方法A和方法B比对很多次来验证方法A是否正确。
采取大量随机样本对比，这里使用了50万个随机样本进行对比。
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[] 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);
}
6，如果有一个样本使得比对出错，打印样本分析是哪个方法出错
7，当样本数量很多时比对测试依然正确，可以确定方法A已经正确。
递归行为的时间复杂度
递归的本质就是用压栈与出栈操作。
当递归操作需要执行子递归操作时，会将当前执行的所有数据压入栈中，这些数据包括当前跑到多少行，当前的参数和函数内的参数变量等等。
当子递归操作返回时进行出栈操作，然后读取出栈后栈顶空间的信息，也就是返回到当初调用的地方。
递归行为时间复杂度的计算
一般的空间复杂度可以使用master公式计算：
master公式 : T(N) = a * T(N / b) + O(N ^ d)
T(N)：父问题的样本量
a：调用模块发生的次数
T(N/b)：子问题的样本量
O(N^d)：除去子问题调用过程外，剩下部分的时间复杂度
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b, a) = d -> 复杂度为O(N^d * logN)
2) log(b, a) < d -> 复杂度为O(N^d)
我们使用递归二分求最大数来举例：
/*
* 递归二分求最大数
*/
public static int getMaxNum(int[] arr, int L, int R) {
// 递归结束条件：只剩下一个数
if(L == R)
return arr[L];
int mid = L +((R - L) >> 1); //位运算取中值
int leftMax = getMaxNum(arr, L, mid); //T(N/2)
int rightMax = getMaxNum(arr, mid + 1, R); //T(N/2)
return Math.max(leftMax, rightMax); //O(1)
}
递归边界：当整个数组被分割成只有一个数时结束递归。
递归逻辑：将数组从中间分割为两个数组，分别取出左右两个数组的最大值，再对比这两个值取最大值。而分割出来的每个数组又继续分割为两个数组，直到分割出来的数组只有一个数为止。
递归时间复杂度的计算：
master公式：T(N) = a * T(N / b) + O(N ^ d)
a：调用模块发生的次数，这里左右两边各执行了一次，a = 2；
b：T(N/b)为子问题的样本量，数组从中间分为相等两份，b = 2；
d：O(N^d)为剩下部分的时间复杂度，这里只执行了取中间值和比较最大值的两个操作，都为常数操作，d = 0；
套用公式以后：T(N) = 2 * T(N / 2) + O(N ^ 0)
满足：log(b,a) > d -> 复杂度为O(N^log(b,a))
时间复杂度即为：O(N^1) = O(N)
参考资料：牛客网左程云初级算法教程
