时间复杂度

1）O(1)

 2）Olon_2_n

3）O(n)

4）O(m + n)

一个循环执行m次，另一个循环执行n次

此时m 和 n都是变量，无法确定谁大谁小。

public void find(m,n){
    for(int i = 0;i < m;i++){
        total += i;
    }
    for(int j = 0;j < n;j++){
        total += j;
    }
}

5）O(n^2)

6）O(nlog_2_n)

外层循环执行m次，内层循环执行n次

public void find(m,n){
    for(int i = 0;i < m;i++){
        total += i;
        for(int j = 0;j < n;j++){
            total += j;
        }
    }
}

时间复杂度的一些经典例题： 

    // O(1)：
    private static void swap(Object[] arr, int i, int j){
        if(i < 0 || i >= arr.length)
            throw new IllegalArgumentException("i is out of bound.");
        if(j < 0 || j >= arr.length)
            throw new IllegalArgumentException("j is out of bound.");
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //O(1):循环次数与传入的n无关，因此仍然是常数级别O(1)
    private void func(int n){
        int count = 0;
        for(int k = 0;k < 100;k++){
            count++;
        }
    }
    // O(N)
    private static int sum(int n){
        if(n < 0)
            throw new IllegalArgumentException("n should be greater or equal to zero.");
        int ret = 0;
        for(int i = 0 ; i <= n ; i ++)
            ret += i;
        return ret;
    }
    // O(N)：O(1/2N)->O(N) 注意这个和O(logN)的区别
    private static void reverse(Object[] arr){
        int n = arr.length;
        for(int i = 0 ; i < n / 2 ; i ++ )
            // O(1)
            swap(arr, i, n - 1 - i);
    }
    // N ^ 2
    private static void selectionSort(Comparable[] arr, int n){
        for(int i = 0 ; i < n ; i ++){ // N
            int minIndex = i;
            for(int j = i + 1 ; j < n ; j ++) // N
                if(arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;

            swap(arr, i, minIndex);
        }
    }
    // O(N)内层循环是常数项：O(N)*O(1) = O(N)
    private static void printInformation(int n){
        for( int i = 1 ; i <= n ; i ++ )
            for( int j = 1 ; j <= 30 ; j ++ )
                System.out.println("Class " + i + " - " + "No. " + j);
    }
    // O(logN) 规律：【变量】每次都在进行/N最终== 0 OR 1,这种都是O(logN)
    private static int binarySearch(Comparable[] arr, int n, int target){
        int l = 0, r = n-1;
        while( l <= r ){
            int mid = l + (r-l)/2;
            if(arr[mid].compareTo(target) == 0) return mid;
            if(arr[mid].compareTo(target) > 0) r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }

    private static String intToString(int num){
        StringBuilder s = new StringBuilder("");
        String sign = "+";
        if(num < 0){
            num = -num;
            sign = "-";
        }
        // O(logN) 符合那个规律
        while(num != 0){
            s.append(Character.getNumericValue('0') + num % 10);
            num /= 10;
        }
        if(s.length() == 0)
            s.append('0');
        s.reverse();
        if(sign == "-")
            return sign + s.toString();
        else
            return s.toString();
    }

    // O(NlogN)
    private static void hello(int n){
        // O(logN)
        // sz = 1
        // sz = 2sz
        // sz = 2sz + 2sz + ...  = n
        for( int sz = 1 ; sz < n ; sz += sz )
            // O(N)
            for( int i = 1 ; i < n ; i ++ )
                System.out.println("Hello, Algorithm!");
    }

    // x = 2
    // x ^ 2 <= num ===>>> x <= sqrt(num)
    // x ++
    // O(根号N)
    private static boolean isPrime(int num){
        for(int x = 2 ; x*x <= num ; x ++)
            if( num % x == 0 )
                return false;
        return true;
    }
    //O(N)
    private int factorial(int N) {//递归阶乘
    	return N < 2 ? N : factorial(N - 1) * N;
    }
    //O(2^N)：递归栈帧的二叉树
    private int fibonacci(int N) {//斐波那契递归
    	return N > 2 ? N : fibonacci(N - 1) + fibonacci(N - 2);
    }

空间复杂度

1）O(1)

变量等于常量时

total = 5;

2）O(n)

变量是array,hashset,list之类的可以存储很多数据的变量时，传入的形参可以改变变量的大小，那么它的空间复杂度会很大

public ovid find(n){
    Set set = new HashSet();
    for(int i = 0;i < n;i++){
        set.add(i);
    }
}

特殊情况：递归时，哪怕没有任何的变量开辟，空间复杂度也是O(N),因为递归调用之前的操作

注意点：

void set(int[] arr){
    //array不算空间复杂度，传入array,不是new的;没有开辟新的内存空间
}

经验总结

时间复杂度分为：最好时间复杂度、最坏时间复杂度、平均时间复杂度；一般关注最坏时间复杂度；当判断时间复杂度时，千万不敢直接只看循环。