[数据结构与算法]时间复杂度和空间复杂度—数据结构

1.算法效率

算法效率包括时间复杂度和空间复杂度

2.算法的时间复杂度（时间效率）

衡量一个算法的运行速率，算法所花费的时间与其语句的执行次数成正比例，并且理论上无法计算

2.1规则

大O的渐进法：用常数1取代运行时间中的所有加法常数；修改后的运行次数函数中，只保留最高项；最高项的系数不是1就去掉系数

2.2算法的情况

最好情况（默认）：任意输入规模的最大运行次数
平均情况：任意输入规模的期望运行次数（不是（最好情况+最坏情况）/2）
最好情况：任意输入规模的最小运行次数

2.3常见时间复杂度计算举例

// 请计算一下func1基本操作执行了多少次？N^2
    void func1(int N){
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0){
            count++;
        }
        System.out.println(count);
    }

// 计算func2的时间复杂度？N
    void func2(int N){
        int count = 0;
        for(int k = 0;k < 2*N;k++){
            count++;
        }
        int M = 10;
        while ((M--)>0){
            count++;
        }
        System.out.println(count);
    }

//计算func3的时间复杂度？M+N
    void func3(int N,int M){
        int count = 0;
        for (int k = 0; k < M; k++) {
            count++;
        }
        for (int k = 0; k < N; k++) {
            count++;
        }
        System.out.println(count);
    }

// 计算func4的时间复杂度？1
    void func4(int N){
        int count = 0;
        for (int k = 0; k < 100; k++) {
            count++;
        }
        System.out.println(count);
    }

// 计算bubbleSort（冒泡排序）的时间复杂度？
//最好情况：N
//最坏情况：N^2
    void bubbleSort(int[] array){
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i-1]>array[i]){
                    Swap(array,i-1,i);
                    sorted=false;
                }
            }
            if(sorted == true){
                break;
            }
        }
    }

 // 计算binarySearch的时间复杂度？logN
    int binarySearch(int[] array,int value){
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end){
            int mid = begin + (end - begin)/2;
            if (array[mid]<value){
                begin = mid + 1;
            }else if (array[mid] > value){
                end = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

理解方式一：

理解方式二：

递归的时间复杂度 = 递归的次数 * 每次递归时执行的次数

// 计算阶乘递归factorial的时间复杂度？N
// 递归的时间复杂度 = 递归的次数(N) * 每次递归时执行的次数(1)
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1) * N;
    }

// 计算斐波那契递归fibonacci的时间复杂度？2^n
// 递归的时间复杂度 = 递归的次数(2^N) * 每次递归时执行的次数(1)
    int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2); 
    }

3.算法的空间复杂度

衡量一个算法所需的额外空间，算法运行过程中临时占用存储空间大小，和问题的规模无关

3.1常见的空间复杂度计算举例

// 计算bubbleSort的空间复杂度？1
    void bubbleSort(int[] array){
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i-1]>array[i]){
                    //Swap(array,i-1,i);
                    sorted=false;
                }
            }
            if(sorted == true){
                break;
            }
        }
    }

// 计算fibonacci的空间复杂度？n
    int[] fibonacci(int n) { 
        int[] fibArray = new int[n + 1]; 
        fibArray[0] = 0; 
        fibArray[1] = 1; 
        for (int i = 2; i <= n ; i++) { 
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; 
        }
        return fibArray; 
    }

// 计算阶乘递归Factorial的空间复杂度？ 
    long factorial(int N) { 
        return N < 2 ? N : factorial(N-1)*N; 
    }