一般情况下，一秒之内相应时间复杂度的算法能解决的数据规模
时间复杂度实验
如何正确的判断算法的时间复杂度
时间复杂度实验：每次将数据规模提高两倍，看时间的变化，以此来验证算法的时间复杂度
以下为代码实例：
测试算法，分别为二分查找O（logN），查找最大值（O（N）），归并排序（O（NlogN））
package com.ice.time;
import static java.lang.Math.min;
public class MyAlgorithmTester {
// O(logN),二分法查找
public static int binarySearch(int arr[], int n, int target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] > target) r = mid - 1;
else l = mid + 1;
}
return -1;
}
// O(N),从数组中寻找最大值
public static int findMax(int arr[], int n) {
assert (n > 0);
int res = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > res)
res = arr[i];
return res;
}
// O(NlogN) 归并排序
private static void __merge(int arr[], int l, int mid, int r, int aux[]) {
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
arr[k] = aux[j];
j++;
} else if (j > r) {
arr[k] = aux[i];
i++;
} else if (aux[i] < aux[j]) {
arr[k] = aux[i];
i++;
} else {
arr[k] = aux[j];
j++;
}
}
}
public static void mergeSort(int arr[],int n){
int[] aux = new int[n];
for(int i = 0;i<n;i++){
aux[i] = arr[i];
}
for(int sz = 1;sz<n;sz+=sz){
for(int i = 0;i<n;i+=sz+sz){
__merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1),aux);
}
}
return;
}
}
工具类，生成随机数组或有序数组，用于测试算法
package com.ice.time;
public class MyUtil {
public static int[] generateRandomArray(int n, int rangeL, int rangeR) {
assert (n > 0 && rangeL <= rangeR);
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * (rangeR - rangeL) + rangeL);
}
return arr;
}
public static int[] generateOrderedArray(int n) {
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
}
}
Main函数，测试算法用的时间并打印，观察时间就可以推测算法的时间复杂度
package com.ice.time;
import static java.lang.Math.pow;
public class Main {
public static void main(String[] args){
for(int i =10;i<=24;i++){
int n = (int) pow(2,i);
int[] arr = MyUtil.generateRandomArray(n,0,100000000);
long startTime=System.currentTimeMillis();
MyAlgorithmTester.selectionSort(arr,n);
long endTime=System.currentTimeMillis();//记录结束时间
System.out.print("data size 2^"+i+" = "+n);
System.out.println("\tTime cost:"+(double)((endTime-startTime)/1000));
}
}
}
对于O(logN)的算法，每次数据规模翻两倍，他的时间变化比例：
大概是一点几倍，当N扩大的非常大时，变化率几乎为0
递归算法的时间复杂度
如果递归中只进行一次递归调用的复杂度分析
典型的例子是递归实现的二分查找，pow函数实现
在递归中进行多次递归调用的复杂度分析
关注递归调用的次数，使用一颗递归树来看递归调用的次数
如果这棵树有N层，那么总调用次数为一个等比数列的和，即2^(n+1)-1,即时间复杂度是一个O(2^n)水平的
那么为什么归并排序一类的递归排序算法，时间复杂度是O(NlogN)呢
原因在于，归并排序的每一层数据规模不变为N，层数实际上是logN
递归排序的递归树
递归函数的时间复杂度分析：主定理（涵盖了所有递归情况的复杂度分析）
均摊复杂度分析
对于有些时间复杂度很高的算法，其实他的时间复杂度高是为了降低其他操作的时间复杂度，这时，需要将这个算法的时间复杂度均摊到其他操作上，这就是均摊复杂度。
- 经典例子：动态数组
- 复杂度震荡
