引入

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

最坏情况和平均情况

比如有一个数列，我们想找数字 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);
    }
}

引入

前面我们讲了普通赋值、输出、打印的时间复杂度、也讲了循环、嵌套循环的时间复杂度，现在我们来看看在函数引用下，时间复杂度有什么不同。

例子

看看下面程序的时间复杂度

int i;  //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
printf("%d\n",count);
}
// 函数就执行了一个 printf 语句 复杂度位 O(1)

上面的循环语句，每执行一次，就会调用一次函数，函数是 1，循环 n 次 1 ，所以上面这个例子的时间复杂度是 O(n) 。

我们再来个复杂点的

int i;  //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
int j;
for (j=0;j<n;j++){
printf("%d",j);
}
}
// 函数内是一个循环，随着 count 的增加，循环次数减少

引入

前一讲，我们介绍了什么是算法的量度，以及如何用渐进函数来看哪些对算法的复杂度影响最大，今天我们就来看看如何计算复杂度。

时间复杂度

• **定义：**在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。所以，算法的时间复杂度，就是算法的时间量度:

  T(n)=O( f(n) )

• **时间复杂度：**它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。称作算法的渐进时间复杂度，简称为时间复杂度。

  f(n) 是问题规模 n 的某个函数（上节我们研究过，能够改变结果的那个函数）

上面的定义很复杂，但只要记住，执行次数==时间就可以了。

引入

前面我们说，算法效率要高，这里的高其实就是算法的执行时间短，时间段效率自然高，那么我们就需要了解，如何判断一个算法的执行效率，也就是执行时间快不快。

事后统计法

我们知道，跑马拉松，选手快不快，是根据到达终点的时间来决定的。算法也一样，我们根据跑完一遍的时间来计算算法的效率。也就是事后统计法。
**事后统计法：**通过设计好的测试程序和数据，利用计算机计时器对不同的算法编程的程序的运行时间进行比较。从而确定算法的效率高低。

事后统计法的缺陷

这种事后统计法是需要测试程序和数据的….
准备测试程序和数据太费功夫了….
因为测试数据和程序要跟算法一对一匹配。
测试失败…不就凉了…

**特别是：**不同的测试环境，测试的结果差别非常大。

引入

前面我们学习了 C 语言的部分知识，我们知道要用计算机解决一个问题大致分为一下几个步骤：

• 具体问题 抽象出 数学模型
• 设计一个算法，解该数学模型
• 编写一个程序
• 调试程序，直到解决问题

那么第一步，找到数学模型，就是解决此问题的关键，我们从模型中找到操作对象，然后找到这些操作对象之间的关系，然后用数学语言去描述它们。

什么是数据结构

程序设计=数据结构+算法

再进一步，数据结构其实研究的就是关系，是数据元素相互之间存在的一种或多重特定关系的集合。

逻辑结构和物理结构

我们把数据结构分为逻辑结构和物理结构

• **逻辑结构：**数据对象中数据元素之间的相互关系，也是我们需要关注和讨论的问题。
• **物理结构：**表示数据的逻辑结构在计算机中的存储形式。

引入

上节，我们介绍了如何根据需要创建有向图、无向图、并且将其结构存储起来，今天我们就将图输出，并且输出一个邻接矩阵，看看我们输入的图对不对。

输出图结构

我们还是分段讲解

输出图的基本信息

//前三个比较简单，就是数据结构体中存储的数据
void print_MG(Graph MG){
if(MG.type == DG)
    {
        printf("图类型 : 有向图:\n");
    }
    else
    {
        printf("图类型：无向图:\n");
    }
    printf("图中的顶点有: %d 个\n",MG.vsnum);
    printf("图中的边/弧有: %d 个\n",MG.esnum);
//输出顶点得集合这里，我们需要用顶点数作为循环结束条件
 printf("顶点的集合:");
    for (i = 1; i <= MG.vsnum; i++){
        printf("%c ", MG.vs[i]);
    }
    }

我们输出了图的一些基本信息

• 输出函数首先接收到图结构体指针
• 图的类型，直接从结构体调用
• 顶点数量、边得数量，也都直接从结构体调用
• 在输出顶点集合的时候，我们需要根据顶点的数量循环输出