引入

我们结束了时间复杂度的学习，了解了常见的时间复杂度的计算以及不同时间复杂度之间的关系，今天我们看看最坏情况和平均情况，以及空间复杂度。

最坏情况和平均情况

比如有一个数列，我们想找数字 1

最好情况：数列是从1~10排列，找第一个就找到1了，O(1)就搞定。
最坏情况：最坏的就是数列是从10~1排列，找到最后一个 n 才找到10，那复杂度就是O( n )。
平均情况：我们期望运行的时间，比如我希望3分钟搞定。
最坏运行时间：这是一种保证，也就是说，我的算法在最坏情况也，需要多少时间搞定，通常情况下，我们说的运行时间，都是最坏运行时间。

算法的空间复杂度

在写代码的时候，我们可以用空间换取时间，当然也可以用时间换取空间。

#include <stdio.h>
int main(){
    int year;
    printf("请输入年份（如2018）：\n");
    scanf("%d",&year);
    if((year%4==0 && year%100!=0 )|| year%400==0){
        printf("%d年是闰年！",year);
    }else{
        printf("%d年不是闰年！",year);
    }
}

这是一个很简单的计算闰年的算法，根据输入的值进行计算，然后判断。我们换一种方式

#include <stdio.h>
int main(){
    int year[2050];
    for(int i=0;i<2050;i++){
        if((i%4==0&&i%100!=0)||i%400==0){
            year[i]=1;
        }else{
            year[i]=0;
        }
    }
    //我们上面通过了一个 for 循环来将2050年所有是闰年的数都包含在了这个数组中。
    int year_in;
    printf("请输入年份:\n");
    scanf("%d",&year_in);
    if(year[year_in]==1){
        printf("%d年是闰年！",year_in);
    }else{
        printf("%d年不是闰年！",year_in);
    }
    // 直接判断即可，不用计算
}

第二种算法，我们提前准备了哪一年是不是闰年的数据库，存储在内存中，然后直接调用即可，不用计算。

时间复杂度： 结果靠计算，每一次都要计算，花费的时间长，但不占用内存空间。
空间复杂度： 结果不用计算，所有结果都存储在内存中，不需要每次都计算。花费时间短，但需要占用内存空间，这就是空间复杂度。

那么究竟哪一种比较好呢？这就要根据实际情况了，如果内存很大，算力很小，那算法就多占用空间复杂度，反之，则多占用时间复杂度。

算法的时间复杂度
通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作S( n )=O(f(n))，感觉和时间复杂度差不多。
n 表示问题的规模
f( n )表示 n 所占用的空间函数

通常情况下：

时间复杂度表示：运行时间的需求
空间复杂度表示：空间需求
如果让我们求一个算法的复杂度，往往指的是时间复杂度。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。