Fabian备忘录

人类资格证考核中

一、数据结构概述

发表于 更新于 分类于 ，
本文字数： 4.7k

基本概念

数据结构的基本概念

数据

  信息的载体。计算机程序加工的原料。

数据元素

  数据的基本单位；由若干数据项组成；

数据对象

  相同性质的数据元素的集合；

数据类型

  值的集合和此集合的一组操作的总称。 以bool为例：值的集合：true和false；操作：与、或、非

  • 原子类型：不可再分：如int、bool；
  • 结构类型：可以再分，如struct；
  • 抽象数据类型：抽象数据组织和相关操作。ADT，只考虑结构和运算，不考虑存储结构。

数据结构

  相互之间存在一种或多种特定关系的数据元素的集合。数据结构只关心数据之间的关系，不关心内容。

数据结构的三要素

逻辑结构

   描述元素之间的逻辑关系，独立于计算机。

  • 集合：没有什么关系
  • 线性结构：一对一
  • 树形结构：一对多
  • 图状结构：多对多

存储结构

  逻辑结构的计算机实现。

  顺序存储必须连续，非顺序存储可以离散；存储结构影响空间分配的方便程度（增删改）；存储结构影响对数据的运算（查询）；

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

运算

  包括定义和实现；定义针对逻辑结构，表示功能（增删改查）；实现针对存储结构

算法

算法的概念

程序=数据+算法

  • 数据：描述问题，存入计算机；
  • 算法：高效处理数据，是求解问题的步骤；

算法的五大特性：

  1. 有穷性：算法必须有穷，程序可以无穷
  2. 确定性：相同输入必须相同输出
  3. 可行性
  4. 输入：有零个或多个输入
  5. 输出：有一个或多个输出

时间复杂度

评价时间开销与问题规模n之间的关系。

时间复杂度的计算

  语句的频度就是该语句在算法中被重复执行的次数。算法中所有语句的频度之和就是T(n)。时间复杂度就是分析的数量级。O代表同阶。

计算步骤：

  1. 找到一个基本操作：基本操作指的是最深层循环；
  2. 分析该基本操作的执行次数x与问题规模n的关系
  3. x的数量级就是算法时间复杂度

常用技巧

  1. 顺序执行的代码只影响常数项，可以忽略；
  2. 只需要挑循环中的一个基本操作，分析它的执行次数x与n的关系；
  3. 多层嵌套循环，只关注最深层循环循环了几次；

 

加法规则：只保留最高阶，且系数变为1。

   

乘法规则：多项相乘，都保留

 

时间复杂度常见大小排序：常对幂指阶

 

 

时间复杂度不仅依赖问题的规模，还与输入数据的性质有关。可以分为最好时间复杂度、平均时间复杂度、最坏时间复杂度。一般只考虑最坏时间复杂度。

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//例1：
void test(int n)
{
    int i=1;            //1次
    while(i<=n){
        i++;            //循环内执行n次
        printf("test"); //循环内执行n次
    }
}

int main()
{
    test(n);
}


第一句顺序执行代码走1次，深层循环内执行了2n次，所以T(n)=2n+1。根据加法规则，只保留最高阶,且系数变为1.

 

1
2
3
4
5
6
7
8
9
10
11
12
//例2:
void test2(int n)
{
    int i=1;
    while(i<=n){
        i++;
        for(int j=1;j<=n;j++){
            printf("test2");
        }
    }
}

最深层循环走次，所以

 

1
2
3
4
5
6
7
//例3
void test3(int n)
{
    while(i<=n){
        i=i*2;    //每次翻倍
    }
}

设最深层循环的语句频度为，则每次变化后，i=，所以由循环条件可得，循环结束时，满足。所以。

 

1
2
3
4
5
6
7
8
9
10
//例4
void fun(int n)
{
	int i = 1;
	while (i * i * i <= n)
	{
		i++;
	}
}

设执行次数为t，则，则，所以。

 

1
2
3
4
5
6
7
8
9
10
11
12
// 例5
void test(inf flag[],int n)
{
    for(int i=0;i<n;i++){  //从第一个元素开始查找
        if(flag[i] == n){
            printf("find!!");
            break;
        }
    }
}

int flag[n]={1,2,...}  //乱序存放1~n

因为是乱序存放。所以要考虑不同情况：

  • 最好时间复杂度：元素n在第一个位置。;
  • 最坏时间复杂度：元素n在最后有个位置。
  • 平均时间复杂度：元素n在任意一个位置的概率相同，都是。

 

1
2
3
4
5
6
7
8
9
10
11
//例6
void fun(int n)
{
	int count = 0;
	for (int k = 1; k <= n; k *= 2) {
		for (int j = 1; j <= n; j++)
		{
			count++;
		}
	}
}

内层循环j<=n与外层循环的变量无关，各自独立。所以对于内层循环来说，每次内层循环都执行n次。

对于外层循环k<=n，假设循环t次，则循环结束时满足，即。

根据乘法原则，T(n)为内层循环乘外层循环，得

 

1
2
3
4
5
6
7
//例7
int fun(int n)
{
	int i = 0, sum = 0;
	while (sum < n) sum += ++i;
	return i;
}

拆基本运算sum += ++i，等价为++i;sum=sum+i; 每执行一次循环，i增1.

i=1时，sum=0+1;

i=2时，sum=0+1+2;

i=3时，sum=0+1+2+3；

所以sum=。所以循环次数t满足sum < n，即，所以时间复杂度为

 

1
2
3
4
5
6
7
8
9
10
11
//例8
void fun(int n)
{
	int sum = 0;
	for (int i = 1; i < n; i *= 2)
	{
		for (int j = 0; j < i; j++) {
			sum++;
		}
	}
}

先拆外层循环，每次自乘2，所以当循环k次后，，需要保证 。

对于内层循环，i取每一个值，内层j都有i个取值，所以内层只需要把每层值相加即可：

  1. i=1时，内层循环1次
  2. i=2时，内层循环2次，总共循环1+2
  3. i=3时，内层循环3次，总共循环1+2+3
  4. i=k时，内层循环k次，总共循环1+2+3+...+，用等比数列求和公式，总共有次

所以当外层循环k次时，内层循环执行次，根据外层循环，得。总共的执行范围在2n以内，所以

 

//例9

，求这个函数的时间复杂度。n为问题规模。为了方便，设n为2的整数次幂。

设,代入后得，由此可得一般递推公式：，进而。即。根据加法规则，。

循环的时间复杂度总结

  • 每一层循环变量都是++：将每一层变量的最大遍历次数相乘
  • 不是每一层循环的变量都是++：对于外层循环每一个值i，求出内层遍历次数，然后求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//每一层循环变量都是++：
for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for (int k = 0; k < n; k++) {

			}
    //这种直接n*n*n

for(int i=0;i<n;i++)
		for(int j=0;j<i;j++)
			for (int k = 0; k < j; k++) {

			}
    //虽然内部j、k的取值和第一层循环有关，时间复杂度应该是n*j*k。可以直接放缩，把j和K都放大到n，最终还是n*n*n

1
2
3
4
5
6
//不是每一层循环的变量都是++:
for (int i = 1; i < n; i *= 2) {
		for (int j = 0; j < i; j++) {

		}
	}

空间复杂度

评价空间开销与问题规模n之间的关系。

  • 普通程序：
    1. 找到所占空间大小与问题规模相关的变量；
    2. 分析所占空间x与问题规模n的关系；
    3. x的数量级就是算法的空间复杂度S(n)；
  • 递归程序：
    1. 找到递归调用的深度x与问题规模n的关系;
    2. x的数量级就是算法的空间复杂度S(n)；
    3. 注：考研大概率空间复杂度就是递归调用的深度。但有的算法各层函数所需存储空间不同，分析方法略有区别
  • 空间复杂度也遵循加法规则、乘法规则

 

 

1
2
3
4
5
6
7
void test(int n)
{
    int i=1;
    while(i<=n){
        i++;
    }
}

这个代码无论问题规模n有多大，算法所需要的运行空间都是固定的常量。算法空间复杂度是。这种常数阶的空间复杂度算法称为原地工作算法。

 

 

1
2
3
4
5
6
void test2(int n)
{
    int flag[n];
    ...
    
}

。只关注存储空间大小与问题规模相关的变量。

 

 

1
2
3
4
5
6
7
void test3(int n)
{
    if(n>1){
        test3(n-1);
    }
    
}

。递归大概率和递归深度有关。每次递归，系统都要开辟一片内存空间存储参数、局部变量等等。

 

 

1
2
3
4
5
6
7
8
void test4(int n)
{
    int flag[n];
    if(n > 1){
        test4(n-1);
    }
    
}

flag[n]的空间大小，会随着递归而发生变化。是个等差数列。