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

1.算法效率

算法效率分为两种：

• 第一种是时间效率，时间效率被称为时间复杂度。
• 第二种是空间效率，空间效率被称作空间复杂度。

??时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以很关注空间复杂度。但是经过计算机的更新换代，计算机的存储容量已经达到了很高的程度，所以现在我们不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

2.1时间复杂度概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，我们需要上机测试才能测出来，不仅麻烦，而且因为这个时间受电脑配置的影响，来衡量算法的时间复杂度也不是很合适。所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，称为算法的时间复杂度。

2.2大O的渐近表示法

public static int 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++;
        }
        return count;
    }

func1的基本操作次数：$f(N)=N^2+2N+10$
实际中，我们计算时间复杂度的时候，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐近表示法。
大O符号：是用于描述函数渐近行为的数学符号。

2.3推导大O阶方法

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O阶的渐近表示法之后，func1的时间复杂度为：$O(N^2)$
通过上面我们发现大O的渐近表示法去掉了那些对结果影响不大的项，简洁明了地表示出了执行次数。
另外，有些算法的时间复杂度存在最好、平均、和最坏情况：
最坏情况：输入任意规模的最大运行次数(上界)
平均情况：输入任意规模的期望运行次数
最好情况：输入任意规模的最小运行次数(下界)
举例： 在一个长度为N的数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

2.4常见的时间复杂度计算举例

示例1

public static int func2(int N){
        int count=0;
        for(int k=0;k<2*N;k++){
            count++;
        }
        int M=10;
        while((M--)>0){
            count++;
        }
        return count;
    }

解析：示例1,基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为O(N)。

示例2

public static int func3(int N,int M){
        int count=0;
        for(int k=0;k<M;k++){
            count++;
        }
        for(int k=0;k<N;k++){
            count++;
        }
        return count;
    }

解析：示例2基本操作执行了N+M次，有两个未知数M和N，时间复杂度O(M+N)。

示例3

 public static int func(int N){
        int count=0;
        for(int k=0;k<100;k++){
            count++;
        }
        return count;
    }

解析：示例3基本操作执行了100次，通过大O阶推导，时间复杂度为O(1)。

示例4

//计算冒泡排序的时间复杂度
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;
            }
        }
    }

解析：假设数组中的元素个数为N，冒泡排序的最好情况为基本操作执行N次；
最坏情况：
第一趟冒泡：执行N-1次
第二趟冒泡：执行N-2次
第三趟冒泡：执行N-3次
…
第N-2趟冒泡：执行2次
第N-1趟冒泡：执行1次
总的执行次数=1+2+…+N-2+N-1=$\frac{N(N?1)}{2}$
时间复杂度一般看最坏情况，通过大O阶方法，该冒泡排序的时间复杂度为O($N^2$)。

示例5

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

解析：二分查找基本操作最好情况执行一次；
最坏情况：

通过计算可得m=$lo{g}_{2}N$，因此该二分查找的时间复杂度为$lo{g}_{2}N$。

示例6

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

解析：一般递归的总执行次数=单次运行时基本语句的执行次数×总的递归次数
该算法的总执行次数=1×N=N，因此时间复杂度为O(N)。

示例7

//计算斐波那契递归fibonacci的时间复杂度
int fibonacci(int N){
return N<2?N:fibonacci(N-1)+fibonacci(N-2);
}

解析：

把左下角的移到右边空缺的地方

那么总的递归次数$f(N)=2^0+2^1+2^2+......+2^{N?3}$
?? ? ? ? ? ? ?? $=2^{N?2}?1$
通过大O阶方法，该斐波那契递归的时间复杂度为$O(N^2)$。

3.空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少字节的空间，而是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐近表示法。

3.1空间复杂度举例

示例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;
            }
        }
    }

空间复杂度计算的核心：对于一般算法，只需要看算法中是否申请额外的空间。
一般递归空间复杂度的计算方法：
单次递归需要的空间×递归的深度
深度其实就是开辟的栈帧个数。
解析：示例1开辟了常数个额外空间，所以空间复杂度为O(1)。

示例2

long[] fibonacci(int n){
        long[] fibArray=new long[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;
    }

解析：该算法动态开辟了N个空间，空间复杂度为O(N)。

示例3

long factorial(int N){
return N<2?N:factorial(N-1)*N;
}

解析：递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间，空间复杂度为O(N)。

常见的时间复杂度：$O(1)、O(lo{g}_{2}N)、O(N)、O(Nlo{g}_{2}N)、O(N^2)、O(N^3)、O(2^N)、O(N!)$
常见的空间复杂度：$O(1)、O(N)、O(N^2)$