（2013中科大）数据结构是具有结构的数据对象（X）

解析：这个说法有些模糊，通常数据结构是计算机存储、组织数据的方式，它不仅仅是一个“具有结构的数据对象”，还涉及到数据的运算和操作。数据结构包括数据的逻辑结构、数据的物理存储结构以及数据上定义的操作。所以，仅仅说数据结构“数据结构是具有结构的数据对象”是不全面的。

数据结构的三要素

1.1.5逻辑结构

数据的逻辑结构：数据元素之间的逻辑关系（2013中科大）。逻辑结构独立于计算机，与数据的存储无关。

（2019广东工业大学）与数据元素本身的形式、相对位置和个数无关的是：数据逻辑结构

解析：所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构；

所谓数据的存储结构，是指数据的逻辑结构在计算机存储空间中的存放形式，与数据元素本身的形式、相对位置和个数有关，逻辑结构与物理存储无关

逻辑结构的种类

（一）线性结构：线性表，栈，队列，双队列，串（一维数组)

（2016南京邮电大学）：下列数据中，（C）是非线性数据结构。

A：栈 B：队列 C：完全二叉树

解析：数据结构中，节点与节点间的相互关系是数据的逻辑结构。数据的逻辑结构分为两类:线性结构——线性表、栈、队列、串，

非线性结构——树、图。

完全二叉树是一种特殊的二叉树，是非线性数据结构;

栈、队列显然属于线性结构。

一对一：结构中的数据元素之之间存在一个对一个的关系，有且仅有一个开始和一个终端点。

除第一个元素外，其他元素有且只有一个前趋；

除最后一个元素外，其他元素有且只有一个后继！

（二）非线性结构：树形结构、图状结构（网状结构）、二叉树

一个结点可能有多个直接前趋和直接后继

①树形结构：一对多

结构中的数据元素之间存在一个对多个的关系。

②图状结构（网状结构）：多对多

结构中的数据元素之间存在多个对多个的关系。

（三）其他结构：集合

①集合：也可用其他结构来表示

结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

（2013中科大）数据的逻辑结构与数据元素本身的内容和形式无关。

数据的逻辑结构只关心数据之间的逻辑关系，而不关心数据元素本身的内容和形式。

1.1.6物理结构（存储结构）

数据元素及其关系（数据结构）在计算机中的表示（又称映象）称为数据的物理结构或存储结构

（2014陕师大）以下术语中，与数据的存储结构无关的是（C）

A：顺序栈 B：哈希表 C：数 D：单链表

解析：数据的存储结构通常指的是数据元素在计算机内存中的存放方式，包括顺序存储和链式存储等。

顺序存储结构，如数组和顺序栈，是将数据元素存放在连续的存储单元中。

链式存储结构，如单链表、树和哈希表，是将数据元素存放在可以是分散的存储单元中并通过指针(或引用)将它们连接起来。
在给出的选项中:
A.顺序栈是一种顺序存储结构，因为它使用连续的内存空间来存储数据。
B.哈希表是一种链式存储结构，因为它使用数组和链表(或开放寻址等)来存储数据。
C.树是一种链式存储结构，因为它通过节点和指针来组织数据。
D.单链表也是一种链式存储结构，因为它通过节点和指针来连接数据元素。
因此，与数据的存储结构无关的术语是C.树。树本身是一种数据结构，可以采用不同的存储方法，例如链式存储(每个节点包含指向其子节点的指针)或数组(如二叉树的完全二叉树表示)。树的概念本身并不局限于特定的存储结构。

（2014北京化工大学）：以下哪一组都是物理结构（C）

A：线性表、二叉树 B：集合、图 C：单链表、散列表 D:线性表、散列表

解析：物理结构是指数据结构在计算机存储空间的物理表示形式，包括数据元素的存储方式和数据元素之间的物理关系。
A.线性表是一种逻辑结构，二叉树是一种物理结构。

B.集合是一种逻辑结构，图可以是逻辑结构也可以是物理结构，但在这里没有明确指出图是逻辑结构还是物理结构，因此选项不明确。
C.单链表和散列表都是物理结构。
D.线性表是逻辑结构，散列表是物理结构。

因此，正确答案是:C 单链表、散列表。

四种基本的存储结构

（一）顺序存储结构（重点）

用一组地址连续的存储单元依次存储线性表的各个数据元素，数据元素之间的逻辑关系由元素的存储位置来表示

C语言中用数组来实现顺序存储结构

优点：节省存储空间。
缺点：不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

（二）链式存储结构（重点）

用一组任意的存储单元存储线性表的数据元素，各个元素之间的关系用指针来表示(这组存储单元可以是连续的,也可以是不连续的)。指针————地址

（三）索引存储结构（了解）

在存储结点信息的同时，还建立附加的索引表。索引——index

索引表的每一项都是索引项

索引项的一般形式是：（关键字、地址）

关键字：可以区分不同数据元素的数据项

例：下方的通讯录就是一个索引表

（四）散列存储结构（哈希存储）（了解）

根据元素的关键字直接计算出该元素的存储地址，也称哈希（Hash）存储

三、逻辑结构与存储结构的关系

1.存储结构是逻辑关系的映象与元素本身的映象。

2.逻辑结构是数据结构的抽象，存储结构是数据结构的实现。

3.两者综合建立了数据元素之间的结构关系

四、数据的运算和实现

施加在

运算：针对逻辑结构，指出运算的功能

运算的实现：针对存储结构，指出运算的具体操作步骤。

针对不同的存储结构，对应的运算实现方式也不一样。

1.1.7数据类型

数据类型就是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

数据类型=值的集合+值集合上的一组操作

C语言中基本数据类型：

整型：int 长整型：long int 短整型：short int

浮点型（单精度）：float 浮点型（双精度）：double 字符型：char 布尔型：bool

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。

例如：bool类型的值为：true、false。可进行的操作：与、或、非...

作用：

约束变量或常量的取值范围；约束变量或常量的操作

1.1.8抽象数据类型（ADT）

抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。与其在计算机内部如何表示无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

抽象数据类型 = 数据的逻辑结构 + 抽象运算（运算的功能描述）

抽象数据类型的形式定义

用三元组表示（D，S，P）：D是数据对象，S是D上的关系集，P是对D的基本操作集。

定义抽象数据类型：


ADT抽象数据类型名{
        数据对象：<数据对象的定义>
        数据关系：<数据关系的定义>
        基本操作：<基本操作的定义>
}ADT抽象数据类型

数据对象和数据关系的定义用伪码（伪代码）描述。

基本操作的定义格式为：


基本操作名（参数表）
    初始条件：<初始条件描述>
    操作结果：<操作结果描述>

赋值参数只为操作提供输入值；

引用参数以&打头，除了可以提供输入值，还将返回操作结果。

三种抽象数据类型

（一）原子类型：属于原子类型的变量的值是不可以分解的。

（二）固定聚合类型：属于固定聚合类型的变量，其值由确定数目的成分按某种结构组成

（三）可变聚合类型：构成可变聚合类型“值”的成分的数目不确定。比如定义一个“有序整数序列”的抽象数据类型，其中序列的长度是可变的。

1.1.9多形数据类型

多形数据类型是指其值的成分不确定的数据类型。一个抽象数据类型里面的元素可以是整数或字符或字符串，甚至更复杂地由多种成分构成（只要能进行关系运算即可）

1.2.0抽象数据类型的表示与实现

（一）预定义常量和类型


//函数结果状态代码
#define    TURE           1
#define    FALSE          0
#define    OK             1
#define    ERROR          0
#define    INFEASIBLE     -1
#define    OVERFLOW       -2
//Status是函数的类型，其值是函数结果状态的代码
typedef  int  Status;

（二）数据结构的表示（存储结构）用类型定义（typedef）描述。数据元素类型约定为ElemType，有用户在使用该数据类型时自行定义

（三）赋值语句

简单赋值变量名 = 表达式

串联赋值变量名1 = 变量名2 = ... = 变量名k = 表达式

成组赋值 (变量名1，...，变量名k) = (表达式1，...，表达式k)；

结构名 = 结构名；

结构名 = （值1，...，值k)；

变量名[ ] = 表达式;

变量名[起始下标..终止下标] = 变量名[ 起始下标..终止下标]；

交换赋值变量名 $\leftarrow \rightarrow$ 变量名；

条件赋值变量名 = 条件表达式 ? 表达式 T ：表达式F；

1.2算法与算法分析

1.2.1算法（algorithm）

算法：对特定问题求解方法和步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。


说白了算法就是解决问题的方法和步骤，第一步要怎么做，第二步要怎么做，第三部要怎么做......
然后列出指令的这样一个序列。
例如：
step1：xxx
step2：xxx
step3：xxx
....    ...

1.2.2算法的描述

自然语言：英文、中文

流程图：传统流程图、NS流程图

伪代码：类语言：类C语言（与C语言类似，但缺少了一些必要的语法细节）

程序代码：C语言程序、Java程序......

举例：

自然语言：


举例：用算法求一元二次方程的根
1.输入方程的系数a、b、c
2.判断a是否等于0，如果等于0，则提示不是一元二次方程；不等于0执行第三步
3.计算△=b²-4ac
4.判断△，如果△=0，计算并输出两个相等实根；如果△＜0，输出没有实根；如果△＞0，输出不等实根
5.结束

传统流程图：

NS流程图：

1.2.3算法与程序

算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法 程序是用某种程序设计语言对算法的具体实现。

程序 = 数据结构 + 算法

数据结构通过算法来实现操作，算法根据数据结构设计程序。

1.2.4算法的5个重要特征

（1）有穷性

一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。（算法必须是有穷的，程序可以是无穷的。）

（2）确定性

算法中的每一条指令都必须有确切的含义，无二义性。任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。

（3）可行性

一个算法是能行的，可以执行的。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现的。

（4）输入

一个算法有零个（因为有时候本身自带了输入）或多个的输入，这些输入取自于某个特定的对象的集合。

（5）输出

一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

1.2.5算法设计的要求

（1）正确性（Correctness）

算法应当满足具体问题的需求。程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。

（2）可读性（Readability）

可读性好有助于人对算法的理解，算法主要是为了人的阅读与交流，如果算法晦涩难懂，乱七八糟，很难理解，往往会隐藏很多错误，难以调试与修改

（3）健壮性（Robustness）

输出数据非法时，算法也能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。处理出错的方法，不应该是打印错误信息或异常，并中止程序的执行，而是返回一个表示错误或错误性质的值。

所以，我们要事先预料到可能会出现的问题和错误，事先进行判断，如果有事先处理错误的判断，那么这样的算法就是健壮性好的

（4）效率与低存储量需求（高效率Efficiency）

花尽量少的时间和尽量低的存储需求。

效率：算法执行的时间。 存储量需求：算法执行过程中所需的最大存储空间。

对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。

一个好的算法首先要具备正确性，然后是健壮性，可读性，在这几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。

算法的效率：时间效率、空间效率

时间效率：算法所耗的时间 空间效率：算法执行过程中所耗的存储空间

时间效率和空间效率有时是矛盾的

1.2.6算法效率的度量

（一）事后统计（一般不用）

（二）事前分析估算

算法运行时间 = 一个简单操作所需的时间 x 简单操作次数

算法运行时间 = ∑每条语句执行次数 x 该语句执行一次所需的时间

算法运行时间 = ∑每条语句频度 x 该语句执行一次所需的时间

注：1：简单的操作：赋值，移动，比较等。

2：∑：求和符号。

3：每条语句的执行次数也称语句频度。

4：语句执行一次所需的时间是不固定的。与算法无关，取决于机器的指令性能、速度以及编写程序用的语言，不同语言的生成的代码质量不一样，通常高级语言编写的语言，速度更慢。

1.2.7时间复杂度

时间复杂度： $T(n) = O(f(n))$

一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作： $T(n) = O(f(n))$ 。随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。

$T(n)=O(f(n))\Leftrightarrow \lim_{n \to \infty }\frac{T(n)}{f(n)}=k$ （k为常数）

注：1：O表示“同阶”，是数量级符号，当 $n\rightarrow \infty$ 时 $\frac{T(n)}{f(n)}$ 的极限值为不等于零的常数。

        2：n：问题规模 T(n)：时间开销

3：当问题规模n足够大时，可以只考虑阶数高的部分。常数可化为1，可忽略

        例：T(n) = n²+n+5 = O(n²) + O(n) + O(1) = O(n²)

        4：基本语句：执行次数最多的 问题规模n：n越大算法执行时间越长

n：①排序：n为记录数。②矩阵：n为矩阵的阶数，矩阵阶数越大，执行的时间越长。③多项式：n为多项式的项数。④集合：n为元素个数，元素个数越多，处理时间越长。⑤数：n为树的结点个数。⑥图：n为图的顶点数或边数。

5.语句的频度：该语句重复执行的次数 。

定理1：若 $f(n)=a_{m}n^{m}+a_{m-1}n^{m-1}+...+a_{1}n+a_{0}$ 是m次多项式，则 $T(n)=O(m^{n})$ 忽略所有低次幂项和最高次幂系数，体现出增长率的含义，只考虑最高次项（数学中的抓大头）。

1.2.8计算时间复杂度的方法

1.找出语句频度最大的那条语句作为基本语句

2.计算基本语句的频度，得到问题规模n的某个函数f(n)

3.取其数量级用符号"O"表示

例一：用算法表示两个N x N矩阵相乘


for(i=1; i<=n; ++i)    //n+1次
    for(j=1; j<=n; ++j){    //n(n+1)次
        c[i][j] = 0;    //n*n次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];    //n*n*n次
}

该算法时间消耗为： $T(n)=2n^{3}+3n^{2}+1$ ，当 $n\rightarrow \infty$ 时， $\frac{T(n)}{n^{3}}\rightarrow 2$ ，表示n充分大时，T(n)与n³是同阶或同数量级，引入大“O”记号，则 $T(n) = O(n^{3})$

整个算法的执行时间与该基本操作（乘法）重复执行的次数n³成正比，记 $T(n) = O(n^{3})$

补充：分析以下程序的时间复杂度
for(i=1; i<=n; i++)    
    for(j=1; j<=n; j++){    
        c[i][j] = 0;   
        for(k=1; k<=n; k++)
            c[i][j] = c[i][j] + a[i][k] * b[k][j];    //n*n*n次
}
算法中的基本操作语句为 c[i][j] = c[i][j] + a[i][k] * b[k][j];

$T(n)=O(n^{3})$

级数计算（高数一、三考、数二不考）：首先算 $\sum_{k=1}^{n}1=n$ ，然后算 $\sum_{j=1}^{n}n=n^{2}$ 最后再算 $\sum_{i=1}^{n}n^{2}=n^{3}$ 得 $T(n)=O(n^{3})$

例二：分析以下程序的时间复杂度
for(i=1; i<=n; i++)    
    for(j=1; j<=i; j++) 
        for(k=1; k<=j; k++)
            x = x+1;
$n(n+1)(n+2)=n^{3}+3n^{2}+2n$

最高次是n³，所以 $T(n) = O(n^{3})$

分析：三层嵌套的循环结构。

外层循环 for(i=1; i<=n; i++) 会执行 n 次。

中间层循环 for(j=1; j<=i; j++) 在每一次外层循环迭代中，都会执行 i 次，其中 i 是当前外层循环的迭代变量。因此，随着 i 从 1 增加到 n，中间层循环的总执行次数是 1 + 2 + ... + n = ，这是一个等差数列求和公式，时间复杂度为。

内层循环 for(k=1; k<=j; k++) 在每一次中间层循环迭代中，都会执行 j 次，其中 j 是当前中间层循环的迭代变量。这个循环的执行次数依赖于 j 的值，而 j 的值又依赖于外层循环的变量 i。因此，我们需要对每一层循环进行累加来得到总的操作次数。

为了得到整个算法的时间复杂度，我们需要考虑所有循环的执行次数。最内层循环体（x = x+1;）的执行总次数可以通过累加每一层循环的次数来得到。这相当于计算下面的三重求和： $(\sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{j} 1)$ ,然后算出结果 $T(n) = O(n^{3})$

因为每一项 i*j 对应的 k 循环会执行 j 次，而 j 又依赖于 i，所以最终的操作次数与 n³ 成正比。

例三：分析以下程序的时间复杂度


x = 0; y = 0;
for(int k = 0; k < n; k++)    //for语句本身是n+1次，循环体是n次
    x++;
for(int i = 0; i < n; i++)     //n+1
    for(int j = 0; j < n ; j++)    //(n+1)次,外层每执行一次，他就要执行n(n+1)次
    y++;    //n*n次

$f(n) = n(n+1)\ , T(n) = O(n^{2})$

个人理解分析：

首先这段代码是由两个独立的循环结构，一个是单重循环，另一个是双重循环。

第一个循环：

x = 0; y = 0;
for(int k = 0; k < n; k++)
x++;

这个循环从k=0开始，每次循环k增加1，直到k不再小于n。因此，这个循环会执行n次。在这个循环体内，只有一个简单的操作：x++，这个操作的时间复杂度是O(1)。所以，第一个循环的时间复杂度是O(n)。

第二个循环是一个嵌套循环：
y = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n ; j++)
y++;
外层循环从i=0开始，到i=n-1结束，因此会执行n次。对于外层循环的每一次迭代，内层循环都会从j=0开始，到j=n-1结束，执行n次。所以，内层循环总共会执行n*n = n²次。在内层循环体中，只有一个简单的操作y++，这个操作的时间复杂度是O(1)。因此，第二个循环的时间复杂度是O(n²)。

因为整段代码的时间复杂度由复杂度最高的部分决定，即O(n²)。这是因为当n趋于无穷大时，n²的增长速度远大于n，所以O(n²)是整段代码的时间复杂度，意味着随着输入规模n的增大，代码执行所需的时间将大致按照n的平方的速度增长。

例四：分析以下程序的时间复杂度


void exam(float x[ ][ ], int m, int n ){
    float sum [ ];
    for (int i= 0;i< m; i++ ){    //m次
        sum[i]= 0.0;
        for ( int j= 0;j< n;j++ )    //n次
            sum[i] += x[i][j];    //m*n次
    }
    for(i=0;i< m; i++ )
        cout << i <<":"<<sum [i]<< endl;
}

分析：直接找嵌套层次最深的，本体嵌套最深的是：

for (int i= 0;i< m; i++ ){
sum[i]= 0.0;
for ( int j= 0;j< n;j++ )
sum[i] += x[i][j];
}

外层for (int i= 0;i< m; i++ )，从0到m-1，执行m次。内层 for ( intj= 0;j< n;j++ )，从0到n-1，执行n次。外面的循环每执行一次，内部循环就要执行n次，外面循环一共执行了m次，所以总共执行m*n次。所以 $f(n)=m*n \ , T(n)=O(m*n)$

例五：分析以下程序的时间复杂度


i=1;
while(i<=n)
i=i*2;

分析：若循环执行1次:i = 1*2= 2¹, 若循环执行2次:i=2*2= 2² 若循环执行3次:i = 2*2= 2³ 若循环执行x次:i = $2^{x}$

设i = i * 2;执行的次数为x次，由循环条件 i <= n 知，得 $2^{x}\leq n\ ,x\leq log_{2}n$

$2^{f(x)}\leq n\Rightarrow f(n)\leq log_{2}n$ ,取最大值 $f(n)\leq log_{2}n$

所以该程序的时间复杂度为 $T(n)=O(log_{2}n)=O(lg\, n)$

此处lgn：因为不管以谁为底，都可以看做以10为底再乘一个常数，而常数可以忽略

时间复杂度的三种情况：

（一）最好的时间复杂度：1次，元素在第一个位置，即 $T(n)=O(1)$

（二）最坏的时间复杂度：n次，元素在最后一个位置，即 $T(n)=O(n)$

（三）平均的时间复杂度：假设元素n在任意一个位置的概率相同为 $\frac{1}{n}$ ，循环次数： $x=(1+2+3+...+n)*\frac{1}{n}=\frac{n*(n+1)}{2}*\frac{1}{n}=\frac{n+1}{2}$ 即 $T(n)=O(n)$

平均时间复杂度指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

很多算法的执行时间与输入的数据有关，一般总是考虑最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

对于复杂的算法，可以拆分为几个简单估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：

（一）加法法则：

（二）乘法法则：

1.2.9算法时间效率的比较

当n取的很大时，指数时间算法多项式时间算法在所需时间上非常悬殊

时间复杂度T(n)按数量递增顺序为：（常对幂指阶）

1.3.0空间复杂度

空间复杂度：算法所需存储空间的量度，记作 $S(n)=O(f(n))$ ,其中n为问题的规模（或大小）

算法的原地工作：算法所需内存空间为常量。（选择题会出）

空间复杂度 = 递归调用的深度

算法要占据的空间：

①算法本身要占据的空间，输入/输出，指令，常数，变量等

②算法要使用的辅助空间

例一：将一维数组a中的n个数逆序存放到原数组中


//算法1
for( i = 0; i < n/2; i++){
    t = a[i];
    a[i] = a[n-i-1];
    a[n-i-1] = t;
}

分析： $\left [ \left | a_{1} \right | \left | a_{2} \right | \left | ... \right |\left | a_{n-1} \right | \left | a_{n} \right | \right ]$ 在一个数组里面存放a1，a2，....，an-1，an，然后逆序， $\left [ \left | a_{n} \right | \left | a_{n-1} \right | \left | ... \right |\left | a_{2} \right | \left | a_{1} \right | \right ]$ 就是将a1和an交换位置，a2和an-1交换位置，一直交换下去，总共有n个元素，所以交换到一半就可以了，也就是n/2次，在交换的时候要有一个临时空间，也就是这里面的t，放入存储元素，用这样的一个临时空间来完成交换，也就是辅助空间。

此处的i是小于n/2的，也就是说取不到n/2，假如是偶数，那么最终i会去到n/2 -1的位置；如果是奇数，i最终会取到n/2向下调整的位置，也就是说会与自己进行交换。

空间复杂度：S(n) = O(1)，也称原地工作（算法有常数阶）

算法1就用了一个变量空间 t = a[i]; 也就是说算法的空间复杂度是1，跟n有多少个元素没有关系，它只需要一个临时变量，所以称它为常数阶


//算法2
for(i = 0; i < n; i++)
    b[i] = a[n-i-1];
for(i = 0; i < n; i++)
    a[i] = b[i];

分析：首先数组的下标是从0开始的，a[i]对应的位序实际上是第i+1个

将a数组的 $\left [ \left | a_{1} \right | \left | a_{2} \right | \left | ... \right |\left | a_{n-1} \right | \left | a_{n} \right | \right ]$ ，按照逆序，放入到b数组 $\left [ \left | a_{n} \right | \left | a_{n-1} \right | \left | ... \right |\left | a_{2} \right | \left | a_{1} \right | \right ]$ 里面。因为a[i] = b[i];，所以再把b数组所有的元素，从下标为0的开始，依次放入a数组中。

算法2需要一个辅助数组b[i]，数组b[i]的大小为：数组a有多大，b就有多大。数组a里面有n个元素，数组b也需要有n个元素，所以它跟元素个数n有关系，即S(n)=O(n)

空间效率为一次阶，n的1次方，跟n 是线性相关的n越多，它需要的辅助空间越多

总结：算法1的空间复杂度（常数的空间算法复杂度）要低于算法2的空间复杂度

空间复杂度：S(n) = O(1) < S(n)=O(n)

算法的空间效率：S(n) = O(1) > S(n)=O(n)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/766278