第2章 面试中的复杂度分析

很多同学一提起复杂度分析就头疼，马上想起了《算法导论》中复杂的数学推导。但其实在一般的企业面试中，对复杂度的分析要求并没有那么高，但也是绕不过去的坎儿。在这一章，和大家介绍一下，面试中需要掌握的复杂度分析。…

目录

2-1 究竟什么是大O（Big O）

2-2 对数据规模有一个概念

2-3 简单的复杂度分析

2-4 亲自试验自己算法的时间复杂度

2-5 递归算法的复杂度分析

2-6 均摊时间复杂度分析（Amortized Time Analysis）

2-7 避免复杂度的震荡

2-1 究竟什么是大O（Big O）

到底什么是BigO？

• n表示数据规模

• O(f(n))表示运行算法所需的执行的指令数，和f(n)成正比。

例如：

算法	时间复杂度	所需执行指令数
二分查找法	O(logn)	a*logn
寻找数组中的最大最小值	O(n)	b*n
归并排序	O(nlogn)	c*nlogn
选择排序	O(n2)	d*n2

在学术界，严格的讲，O(f(n))表示算法执行的上界：归并排序算法的时间复杂度是O(nlogn)的，同时也是O(n²)。

在业界，我们使用O来表示算法执行的最低上界，我们一般不会说归并排序是O(n²)的。

2-2 对数据规模有一个概念

如果想在1秒之内解决问题
O(n²)的算法可以处理大约10⁴级别的数据
O(n)的算法可以处理大约10⁸级别的数据
O(nlogn)的算法可以处理大约10⁷级别的数据

空间复杂度

• 多开一个辅助的数组：O(n)

• 多开一个辅助的二位数组：O(n²)

• 多开常量空间：O(1)

递归调用是有空间代价的

public class Main {

    public static void main(String[] args) {

        // 数据规模每次增大10倍进行测试
        // 有兴趣的同学也可以试验一下数据规模每次增大2倍哦:)
        for( int x = 1 ; x <= 20 ; x ++ ){

            int n = (int)Math.pow(10, x);
            String string = Integer.toString(n);

            long startTime = System.currentTimeMillis();

            long sum = 0;
            for( int i = 0 ; i < n ; i ++ )
                sum += i;

            long endTime = System.currentTimeMillis();

            System.out.println("sum = " + sum);
            System.out.println("10^" + x + " : " + (endTime - startTime) + " ms");
            System.out.println("");
        }
    }
}

public class Main2 {

    private static int sum1(int n){

        assert n >= 0;
        int ret = 0;
        for( int i = 0 ; i <= n ; i ++ )
            ret += i;
        return ret;
    }

    private static int sum2(int n){

        assert n >= 0;
        if( n == 0 )
            return 0;

        return n + sum2(n-1);
    }

    public static void main(String[] args) {

        System.out.println(sum1(10000));
        System.out.println(sum2(10000));
    }
}

2-3 简单的复杂度分析

公式：$log_aN=log_ab*log_bN$loga​N=loga​b∗logb​N，其中$log_ab$loga​b是常数。

质数/素数：除了1和它本身之外没有其他约数的数字。

public class Main {

    // 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(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;
    }

    private static void reverse(Object[] arr){

        int n = arr.length;
        for(int i = 0 ; i < n / 2 ; i ++ )
            swap(arr, i, n - 1 - i);
    }

    // O(n^2) Time Complexity
    private static void selectionSort(Comparable[] arr, int n){

        for(int i = 0 ; i < n ; i ++){
            int minIndex = i;
            for(int j = i + 1 ; j < n ; j ++)
                if(arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;

            swap(arr, i, minIndex);
        }
    }

    // O(n) Time Complexity
    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) Time Complexity
    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 = "-";
        }

        while(num != 0){
            s.append(Character.getNumericValue('0') + num % 10);
            System.out.println(s);
            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){

        for( int sz = 1 ; sz < n ; sz += sz )
            for( int i = 1 ; i < n ; i ++ )
                System.out.println("Hello, Algorithm!");
    }


    // O(sqrt(n)) Time Complexity
    private static boolean isPrime(int num){

        for(int x = 2 ; x*x <= num ; x ++)
            if( num % x == 0 )
                return false;
        return true;
    }

    private static boolean isPrime2(int num){

        if( num <= 1 ) return false;
        if( num == 2 ) return true;
        if( num % 2 == 0 ) return false;

        for(int x = 3 ; x * x <= num ; x += 2)
            if( num%x == 0 )
                return false;

        return true;
    }

    public static void main(String[] args) {

        System.out.println(intToString(123));
        System.out.println(intToString(0));
        System.out.println(intToString(-123));

        System.out.println("This is meaning "+Character.getNumericValue('0'));

        if(isPrime2(137)) System.out.println("137 is a prime.");
        else System.out.println("137 is not a prime.");

        if(isPrime2(121)) System.out.println("121 is a prime.");
        else System.out.println("121 is not a prime.");
    }
}

2-4 亲自试验自己算法的时间复杂度

public class MyAlgorithmTester {

    private MyAlgorithmTester(){}

    // O(logN)
    public static int binarySearch(Comparable arr[], int n, Comparable 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;
    }

    // O(N)
    public static Integer findMax(Integer[] arr, int n){

        assert n > 0;

        Integer res = arr[0];
        for(int i = 1 ; i < n ; i ++)
            if(arr[i]> res)
                res = arr[i];
        return res;
    }

    // O(NlogN)
    public static void mergeSort(Comparable[] arr, int n ){

        Comparable[] aux = new Comparable[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, Math.min(i + sz + sz - 1, n - 1), aux);

        return;
    }

    private static void merge(Comparable[] arr, int l, int mid, int r, Comparable[] aux){

        for(int i = l ; i <= r ; i ++)
            aux[i] = arr[i];

        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].compareTo(aux[j]) < 0){ arr[k] = aux[i]; i ++;}
            else          { arr[k] = aux[j]; j ++;}
        }
    }

    // O(N^2)
    public static void selectionSort(Comparable[] arr, int n ){

        for(int i = 0 ; i < n ; i ++){
            int minIndex = i;
            for( int j = i + 1 ; j < n ; j ++ )
                if(arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;

            swap(arr, i, minIndex);
        }

        return;
    }

    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 t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

public class MyUtil {

    private MyUtil(){}

    public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {

        assert n > 0 && rangeL <= rangeR;

        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++)
            arr[i] = (int)(Math.random() * (rangeR - rangeL + 1)) + rangeL;
        return arr;
    }

    public static Integer[] generateOrderedArray(int n) {

        assert n > 0;

        Integer[] arr = new Integer[n];

        for (int i = 0; i < n; i++)
            arr[i] = i;
        return arr;
    }
}

public class Main {

    public static void main(String[] args) {

        // 数据规模倍乘测试findMax
        // O(n)
        System.out.println("Test for findMax:");
        for( int i = 10 ; i <= 28 ; i ++ ){

            int n = (int)Math.pow(2, i);
            Integer[] arr = MyUtil.generateRandomArray(n, 0, 100000000);

            long startTime = System.currentTimeMillis();
            Integer maxValue = MyAlgorithmTester.findMax(arr, n);
            long endTime = System.currentTimeMillis();

            System.out.print("data size 2^" + i + " = " + n + "\t");
            System.out.println("Time cost: " + (endTime - startTime) + " ms");
        }
    }
}

public class Main2 {

    public static void main(String[] args) {

        // 数据规模倍乘测试selectionSort
        // O(n^2)
        System.out.println("Test for Selection Sort:");
        for( int i = 10 ; i <= 16 ; i ++ ){

            int n = (int)Math.pow(2,i);
            Integer[] 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 + "\t");
            System.out.println("Time cost: " + (endTime - startTime) + " ms");
        }
    }
}

public class Main3 {

    public static void main(String[] args) {

        // 数据规模倍乘测试binarySearch
        // O(logn)
        System.out.println("Test for Binary Search:");
        for(int i = 10 ; i <= 28 ; i ++){

            int n = (int)Math.pow(2, i);
            Integer[] arr = MyUtil.generateOrderedArray(n);

            long startTime = System.currentTimeMillis();
            MyAlgorithmTester.binarySearch(arr, n, 0);
            long endTime = System.currentTimeMillis();

            System.out.print("data size 2^" + i + " = " + n + "\t");
            System.out.println("Time cost: " + (endTime - startTime) + " ms");
        }
    }
}

public class Main4 {

    public static void main(String[] args) {

        // 数据规模倍乘测试mergeSort
        // O(nlogn)
        System.out.println("Test for Merge Sort:");
        for( int i = 10 ; i <= 26 ; i ++ ){

            int n = (int)Math.pow(2,i);
            Integer[] arr = MyUtil.generateRandomArray(n, 0, 1<<30);

            long startTime = System.currentTimeMillis();
            MyAlgorithmTester.mergeSort(arr, n);
            long endTime = System.currentTimeMillis();

            System.out.print("data size 2^" + i + " = " + n + "\t");
            System.out.println("Time cost: " + (endTime - startTime) + " s");
        }
    }
}

2-5 递归算法的复杂度分析

不是所有递归的函数都是O(nlogn)。

递归中进行一次递归调用的复杂度分析。如果递归函数中，只进行一次递归调用，递归深度为depth。在每个递归函数中，时间复杂度为T，则总体的时间复杂度为O(T*depth)。

递归中进行多次递归调用：计算调用的次数，可以画出递归树计算。

public class Main {

    // binarySearch
    private static int binarySearch(Comparable[] arr, int l, int r, int target){

        if(l > r)
            return -1;

        int mid = l + (r - l) / 2;
        if(arr[mid].compareTo(target) == 0)
            return mid;
        else if(arr[mid].compareTo(target) > 0)
            return binarySearch(arr, l, mid - 1, target);
        else
            return binarySearch(arr, mid + 1, r, target);

    }

    // sum
    private static int sum(int n){

        assert n >= 0;

        if(n == 0)
            return 0;
        return n + sum(n - 1);
    }

    // pow2
    private static double pow(double x, int n){

        assert n >= 0;

        if(n == 0)
            return 1.0;

        double t = pow(x, n / 2);
        if(n % 2 == 1)
            return x * t * t;

        return t * t;
    }

    public static void main(String[] args) {

        System.out.println(sum(100));
        System.out.println(pow(2, 10));
    }
}

public class Main2 {

    // f
    private static int f(int n){

        assert( n >= 0 );

        if(n == 0)
            return 1;

        return f(n - 1) + f(n - 1);
    }

    /*
    // mergeSort
    private static void mergeSort(Comparable[] arr, int l, int r){

        if(l >= r)
            return;

        int mid = (l+r)/2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
    */

    public static void main(String[] args) {

        System.out.println(f(10));
    }
}

2-6 均摊时间复杂度分析（Amortized Time Analysis）

import java.util.Arrays;

/**
 * Created by liuyubobobo.
 */
public class MyVector<Item> {

    private Item[] data;
    private int size;       // 存储数组中的元素个数
    private int capacity;   // 存储数组中可以容纳的最大的元素个数

    public MyVector(){
        data = (Item[])new Object[100];
        size = 0;
        capacity = 100;
    }

    // 平均复杂度为 O(1)
    public void push_back(Item e){

        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    public Item pop_back(){

        if(size <= 0)
            throw new IllegalArgumentException("can not pop back for empty vector.");

        size --;
        return data[size];
    }

    // 复杂度为 O(n)
    private void resize(int newCapacity){

        assert newCapacity >= size;
        Item[] newData = (Item[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];

        data = newData;
        capacity = newCapacity;
    }

    // 注意：Java语言由于JVM内部机制的因素，测量的性能时间有可能是跳跃不稳定的。
    public static void main(String[] args) {

        for( int i = 10 ; i <= 26 ; i ++ ){

            int n = (int)Math.pow(2,i);

            long startTime = System.currentTimeMillis();
            MyVector<Integer> vec = new MyVector<Integer>();
            for(int num = 0 ; num < n ; num ++){
                vec.push_back(num);
            }
            long endTime = System.currentTimeMillis();

            System.out.print(n + " operations: \t");
            System.out.println((endTime - startTime) + " ms");
        }
    }
}

2-7 避免复杂度的震荡

import java.util.Arrays;

/**
 * Created by liuyubobobo.
 */
public class MyVector<Item> {

    private Item[] data;
    private int size;       // 存储数组中的元素个数
    private int capacity;   // 存储数组中可以容纳的最大的元素个数

    public MyVector(){
        data = (Item[])new Object[100];
        size = 0;
        capacity = 100;
    }

    // 平均复杂度为 O(1)
    public void push_back(Item e){

        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    public Item pop_back(){

        if(size <= 0)
            throw new IllegalArgumentException("can not pop back for empty vector.");

        Item ret = data[size-1];
        size --;

        // 在size达到静态数组最大容量的1/4时才进行resize
        // resize的容量是当前最大容量的1/2
        // 防止复杂度的震荡
        if(size == capacity / 4)
            resize(capacity / 2);

        return ret;
    }

    // 复杂度为 O(n)
    private void resize(int newCapacity){

        assert newCapacity >= size;
        Item[] newData = (Item[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];

        data = newData;
        capacity = newCapacity;
    }

    // 注意：Java语言由于JVM内部机制的因素，测量的性能时间有可能是跳跃不稳定的。
    public static void main(String[] args) {

        for( int i = 10 ; i <= 26 ; i ++ ){

            int n = (int)Math.pow(2,i);

            long startTime = System.currentTimeMillis();
            MyVector<Integer> vec = new MyVector<Integer>();
            for(int num = 0 ; num < n ; num ++){
                vec.push_back(num);
            }
            for(int num = 0 ; num < n ; num ++){
                vec.pop_back();
            }
            long endTime = System.currentTimeMillis();

            System.out.print(2 * n + " operations: \t");
            System.out.println((endTime - startTime) + " ms");
        }
    }
}