6.1.5 交换函数 swap(a, b)

强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 6.1.5 交换函数 swap(a, b)

函数定义如下(不用掌握)：

void swap(int &amp;a, int &amp;b)
{
    int temp = a;
    a = b;
    b = temp;
}


<!-- page 253 -->

让我们看看这两种不同的写法

① 不使用 swap 函数：

//冒泡排序
for(int i = n-1; i &gt; 1; i--)
for (int j = 0; j &lt; i; j++)
if (A[i] &lt; A[j])
{
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}


② 使用 swap 函数：

//冒泡排序
for(int i = n-1; i &gt; 1; i--)
for (int j = 0; j &lt; i; j++)
if (A[i] &lt; A[j]) swap(A[i], A[j]);


<!-- page 254 -->

## 6.2 复杂度的估算

考试中经常要求时间和空间复杂度，如无特殊说明，数据结构大题中问的时间和空间复杂度都
是最坏情况下的复杂度，只有一个例外：快速排序（考虑平均复杂度，或者给快速排序增加一7
种优化)。

在计算机学科中，log₂n常常写作logn，他们都是以2为底的对数运算。

## 6.2.1 时间复杂度

时间复杂度是对时间增长速度的一个估计。时间复杂度为O(f(n))表示该算法执行的指令数的上界是O(f(n))级别的，可以简单的用极限理解，若所有指令总执行次数T，时间复杂度为O(f(n))的算法表示 = K(K 为常数)。 X

例如 T1 = n² + n, T2 = 2n² − n，通过极限的思想得到这两个算法的 f(n) = n² 即时间复杂度都是O(n²)，常数K1=1，K2=2，K1≠K2，但复杂度是一样的，所以常数系数不影响复杂度；本例中时间复杂度只有最高次决定，所以较低次项不影响复杂度。总之我们就是需要查看算法的指令执行次数的最高次项（而不考虑他的系数）。

常见时间复杂度：O(logn) < O(n) < O(nlogn) < O(n²) < O(n³)。

O(log2n)和 O(log3n)其实是相等的，因为 log2n = log23×log3n，而 log23 是常数，所以O(log2n) = O(log3n)，考虑复杂度时，所有的log 都尽量写成 log2n 或者 logn 的形式。

对于考试时写的代码，时间复杂度只需要考虑循环和递归次数。

## 循环次数

所有循环都可以写成for循环。

以链表和数组为例，如果我们知道访问次数，尽量用for循环

for (i = 0; i &lt; n; i++)
cout&lt;&lt;A[i];


如果不知道访问次数而是满足某个条件时终止，用while 循环

while (p != NULL)
{
    cout &lt;&lt; p-&gt;data;
    p = p-&gt;next;
}


①对于多层for 循环，如果每一层的变量都是自增1，则直接把每层执行次数相乘

<!-- page 255 -->

for (i = 0; i &lt; n; i++)
for (j = 0; j &lt; n; j++)
for (k = 0; k &lt; n; k++)
if (A[i][j] &gt; A[i][k] + A[k][j])
A[i] [j] = A[i][k] + A[k][j];


他的每一层都是变量自增，且变量都是从0\~n-1共n 次，所以总次数是n³，时间复杂度是O(n3)。 道

②对于多层for 循环，如果每一层的变量都是自增1，但第二三层变量取值范围和第一层变量有关

for (i = 0; i &lt; n; i++)
for (j = 0; j &lt; i; j++)
for (k = 0; k &lt; j; k++)
if (A[i][j] &gt; A[i][k] + A[k][j])
A[i][j] &gt; A[i][k] + A[k][j];


时间复杂度和第 ① 种一样，但不用考虑具体次数，时间复杂度是 O(n³)。

③对于两层循环，变量不是自增1(这种情况主要针对小题)

// 22 考研真题
for (i = 1; i &lt; n; i*=2)
for (j = 0; j &lt; i; j++)
sum++;


需要讨论第一层变量i取不同值时，j的取值有 x种，然后对x 求和。比如本题，i = 1,2,4，8...2k(2k < n ≤ 2k+1)时，第二层j有i个取值，所以总次数是对i 求和，即 T = 1+2+4+2k=2k+1-1，n < T < 2n，时间复杂度就是 O(n)。 人

<!-- page 256 -->

## 递归次数

递归总次数和时间复杂度有关，而最大递归层数和空间复杂度有关。

对于树中序遍历的递归写法，每个结点都会调用一次所以总共调用次数是O(n)级别的，时间复杂度是 O(n)。

void InOrder(BTNode *p)
{
    if (p == NULL) return;
    InOrder(p-&gt;lchild);
    visit(p); // 对 p 结点的访问等
    InOrder(p-&gt;rchild);
}


<!-- page 257 -->

## 6.2.2 空间复杂度

只算额外空间开销，不考虑题目中已经给出的数据所占的空间，比如题目中给出了一个数组，这个数组是不计入空间复杂度的。 尊

## 定义的数组、链表

单个定义的变量都不需要考虑，但定义的数组中元素个数以及链表中结点个数都要计入空间复杂度中。 X

int i, j, k; //单个变量不考虑
// 数组考虑元素个数，空间复杂度0(n)
int a[n];
//链表考虑结点个数,空间复杂度0(n)
Node* L = (Node*)malloc(sizeof(Node));
Node* p = L;
for (int i = 0; i &lt; n; i++)
{
    p-&gt;next = (Node*)malloc(sizeof(Node));
    p = p-&gt;next;
}


## 递归层数

是在递归栈中最多出现多少个过程函数，层数和总次数比较见时间复杂度的递归次数。

对于树中序遍历的递归写法，每个结点都会调用一次所以总共调用次数是O(n)级别的，时间复杂度是 O(n)，而递归使用的层数最多是树高 h，空间复杂度是 O(h)，但 h 是不确定的，而我们又知道 h≤n，最坏情况下高度 h=n，因此空间复杂度为 O(n)。 K

void InOrder(BTNode *p)
{
    if (p == NULL) return;
    In0rder(p-&gt;lchild);
    visit(p); // 对p结点的访问等
    InOrder(p-&gt;rchild);
}


<!-- page 258 -->

## 6.3 书写

## 6.3.1 题目要求

考试的代码题一般分为三小问：

第一小问：设计思想

主要介绍逻辑，告诉老师你用了什么，比如快速排序，重要的是让老师知道你用的方法是什么。

第二小问：描述算法

注释要详实，用来介绍变量、过程的作用，提示老师。对于快速排序和折半查找（注意是否查找成功）可以直接默写，过程函数不需要改动，注意调用的参数即可。

第三小问：求时间和空间复杂度

直接写复杂度，不用过程，要检验是否符合代码。

<!-- page 259 -->

## 6.3.2 作答建议

## 本节指引

本节不仅会教你如何解题，更重要的是：如果你不敢面对算法题、总想着数据结构还没学好，该方法旨在帮助你克服对代码题的心理恐惧和无力感。

1.化解“无从下手”的绝望感：把一个大问题拆解成多个小任务，让你不再觉得面对的是一座无法翻越的高山，而是一级级可以攀登的阶梯。每完成一步，你都会获得一份正向反馈，这份小小的成就感会驱动你继续前进。

2.降低“害怕犯错”的恐惧：先用草稿纸思考，再用文字描述，最后才动手写代码。这个过程允许你在低成本的环境中犯错和调整，很多时候你写不出来代码，不是你完全不会，可能只是某些模块没掌握。你可以准确定位问题，并针对性地学习和掌握，无需再害怕犯错。

这套方法不是让你立刻变得完美，而是让你变得比昨天更好，早晚有一天能够彻底拿下算法题。请今天开始，勇敢地面对它！

我建议同学们先思考清楚整个算法需要做哪些事情已经对应流程，分析完复杂度再开始写。

对于能想出思路但不会下笔的同学我有如下建议，可以练习模块化写法，分为如下步骤：

1.想好思路之后在草稿纸上写简易流程图，把一道题分为不同的步骤，估算复杂度并确保方法和复杂度都正确。

2.根据流程图在答题卡上回答第一小问设计思想，适当扩充描述。

3根据流程图在答题卡上回答第二小问描述算法，按照步骤尝试写出每一块的代码，这样可以减少代码的涂改。

4.写上时间和空间复杂度。

在练习时使用此方法有助于找到自己的问题到底是理不清过程还是具体哪一块代码不会写（比如说折半查找)，这有助于我们针对性练习对应模块。

以真题 2011.47 为例：

(15 分)一个长度为L（L≥1）的升序序列S，处在第「L/21个位置的数称为S的中位数。例如，若序列S1=(11，13，15，17,19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6，8，20)，则S1 和S2 的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。 计

<!-- page 260 -->

<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>做题思路</td><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>预计得分</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>快速排序</td><td rowspan=1 colspan=1>O(nlogn)</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>11</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>多指针法+新数组</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>13</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>多指针法</td><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>14</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>折半查找</td><td rowspan=1 colspan=1>O(logn)</td><td rowspan=1 colspan=1>O(1)</td><td rowspan=1 colspan=1>15</td></tr></table>

## 步骤1：思考、在草稿纸上写流程图

想好思路之后在草稿纸上写简易流程图，把一道题分为不同的步骤，估算复杂度并确保方法和复杂度都正确。 V

位数。因此归并两个有序数组得到合并数组，然后输出中位数。

【解法2】优化解：多指针法，归并两个数组

流程：

1. 合并两个数组。

2. 输出中位数。

详细流程：

1. 合并两个数组。a. 设置i、j、k分别指向各数组最小元素。b. 循环将最小值存入新数组。c. 将剩余元素依次存入数组 C 中。 1

2. 输出中位数。时间复杂度为 O(n)，空间复杂度为 O(n)。

## 步骤2：在答题卡上写第1小问

根据草稿纸的简易流程图扩写变成第1小问，在写的时候需要慢慢考虑实现问题。

1. 合并两个数组，得到新的升序数组C。

a. 设置i、j、k分别指向 A、B、C 最小元素。

b. 只要A、B 都存在元素就循环比较其最小值，将更小者存入数组C。

c. 将 A、B 数组中剩余元素依次存入数组 C 中。

2. 输出 C[n-1]。

## 步骤3：在答题卡上写第2小问

<!-- page 261 -->

根据简易流程图和第1小问，一个模块一个模块将过程变为代码。


## 步骤4：在答题卡上写第3小问

书写时间和空间复杂度

(3)时间复杂度：O(n)空间复杂度：O(n)

## \*步骤5：复习时复盘

基础不太扎实的同学，如果做不出来算法题，可以分析到底是哪里出了问题：

不能很好的理清楚步骤、流程：

这一类同学思路有问题，需要优先练习思路，可以先尽可能多做题（真题+习题），只写步骤，不写代码，当你大部分题目都可以写出流程时再做下一步。 KV

能写出详细的流程，但无法将对应流程转化为代码：

这一类同学思路没问题但代码写太少了，需要把所有真题练习完，如果某一道题过程没问题而只是具体模块不会写代码，则可以针对性的练习这一块代码，如：快速排序、折半查找，只要所有的模块都能写出代码，完整的代码肯定也没问题。

大部分畏惧代码题的同学都是因为自身在很多地方都有问题，自己只知道写不出来，但是哪里有问题不知道，这样的话也不能够有的放矢的分析，而总是想着我重新学一遍数据结构说不定就会了，但其实我们更需要的是针对性练习，首先知道自己的问题在哪：是过程不会写还是具体某个模块有问题。在此基础上再针对性复习就能事半功倍。

<!-- page 262 -->

## 6.4 复习思维导图

<!-- page 263 -->


<!-- page 264 -->