一般情况下，一秒之内相应时间复杂度的算法能解决的数据规模

时间复杂度实验

如何正确的判断算法的时间复杂度

时间复杂度实验：每次将数据规模提高两倍，看时间的变化，以此来验证算法的时间复杂度

以下为代码实例：

测试算法，分别为二分查找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

递归排序的递归树

递归函数的时间复杂度分析：主定理（涵盖了所有递归情况的复杂度分析）

均摊复杂度分析

对于有些时间复杂度很高的算法，其实他的时间复杂度高是为了降低其他操作的时间复杂度，这时，需要将这个算法的时间复杂度均摊到其他操作上，这就是均摊复杂度。

• 经典例子：动态数组
• 复杂度震荡