【数据结构】第一章——习题演练

导言

本篇章题目出自：王道考研系列丛书——《2024年数据结构考研复习指导》课后习题。
题目主要考察的是对时间复杂度的分析，在前面的篇章中我们知道时间复杂度是与问题规模n和输入的值k有关的，但是我们在分析时间复杂度时都是以最坏时间复杂度进行分析，这样能确保算法的运行时间不会比它更长。

分析方法与步骤

对于时间复杂度的分析，我自己的经验是通过递进语句与条件判断语句来找出程序运行时间与问题规模之间的关系。
因为我们在分析时间复杂度是都是分析的最坏时间复杂度，所以此时是忽略输入值带来的影响，默认初始值为最小值，之后我们只需要确认最小值是如何通过递进条件来逼近问题规模就行了。
这里我通过下面两个列子来说明：

单层循环

void Func(int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("hello world\n");
	}
}

在这个函数中，我们想要分析它的时间复杂度，可以按照以下步骤一步一步来分析：

第一步：找到问题规模

• 我们从条件语句i < n;可以很容易的得到这个问题的问题规模为n，当i = n 成立时循环结束；

第二步：找到递进方式

• 通过对象语句int i = 0;和递进语句i++; 我们能够知道，此时的对象需要每执行一次递进都会在原先的基础上增加1；

第三步：找到执行次数与问题规模之间的关系

• 当变量 i 执行 1 次递进语句时，i 就会从0变成1；
• 当变量 i 执行 t 次递进语句时，i 就会从0变成 t；
• 当t = n 时，i 就会从0变成 n；
  因此执行次数与问题规模之间的关系就是t = n；

第四步：写成反函数

• 在得到执行次数与问题规模之间的关系表达式之后，我们就需要找到表达式的反函数，并将其改写成$t=T(n)$的形式。
  改写的方式很简单，我们只需要将执行次数 t 的系数变为1就行。
  比如这里的$t=n$，此时 t 的系数就已经是1了，所以我们可以直接写成$t=T(n)=n$；

第五步：改写表达式

• 在得到执行次数 t 关于问题规模 n 的表达式之后，我们只需要在问题规模这一侧在n的前面加一个$O$；
  此时我们就能得到$T(n)=O(n)$；

嵌套循环

void Func2(int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("one piece\n");
		}
	}
}

在这个函数中我们可以看到，此时函数是由两层循环组成的，我们要分析它就需要由外到内，逐层分析；

1. 外层循环

   1. 问题规模

   通过判断语句可知，外层循环的问题规模为n；

   2. 递进方式

   通过对象语句和递进语句可知，外层循环的递进方式是从0开始每次增加1；

   3. 执行次数与问题规模的关系

   由递进方式可知，当执行t次时，变量 i 就会从0变成 t ，当t = n时，就可以得到它们之间的关系为t = n；

   4. 写成反函数

   因为此时t的系数已经为1，所以我们可以很容易得到表达式 $t=T(n)=n$；

   5. 改写表达式

   现在我们只需要在 n 前面加一个O就可以得到时间复杂度的表达式了，即$T(n)=O(n)$；

2. 内层循环

   1. 问题规模

   通过判断语句可知，内层循环的问题规模为n；

   2. 递进方式

   通过对象语句和递进语句可知，内层循环的递进方式是从0开始每次增加1；

   3. 执行次数与问题规模的关系

   由递进方式可知，当执行t次时，变量 i 就会从0变成 t ，当t = n时，就可以得到它们之间的关系为t = n；

   4. 写成反函数

   因为此时t的系数已经为1，所以我们可以很容易得到表达式 $t=T(n)=n$；

   5. 改写表达式

   现在我们只需要在 n 前面加一个O就可以得到时间复杂度的表达式了，即$T(n)=O(n)$；

3. 合并表达式
   现在我们需要分析一下这里合并表达式的方式，具体是通过加法规则进行合并还是通过乘法规则进行合并；

嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。对于这个代码来说，外层循环要执行n次，每执行一次，内层循环就要执行n次，即外层循环执行n次，内层循环就要执行n+n+n+……+n=n*n次；

所以此时我们需要使用乘法规则来进行合并，即$T(n)=O(n)\ast O(n)=n\ast n=n^2=O(n^2)$；

现在大家应该对时间复杂度的分析有点感觉了，接下来我们就通过下面的习题来巩固一下；

单项选择题

题目1

1.以下算法的时间复杂度为（）

`void fun(int n)
{
	int i = 1;
	while (i <= n)
	{
		i = i * 2;
	}
}`

$A.O(n)$
$B.O(n^2)$
$C.O(nlo{g}_{2}n)$
$D.O(lo{g}_{2}n)$

题目解析

这一题是一个单层循环的题目，下面我们按步骤来对这个循环进行分析；

第一步：问题规模

• 通过条件语句可知，这里的问题规模为n；

第二步：递进方式

• 通过对象语句和递进语句可知，此时的递进方式是从1开始，每次扩大2倍，当执行t次时，就要扩大$2\ast 2\ast 2\ast \dots \dots \ast 2=2^t$倍；

第三步：问题规模与执行次数的关系

• 当执行t次后，变量i与n相等时，可以得到$2^t=n$;

第四步：写成反函数

• $2^t=n$这个表达式我们需要给等式两边同时取对数，即可得到$t=T(n)=lo{g}_{2}n$；

第五步：改写表达式

• 此时我们在$lo{g}_{2}n$的前面加一个O就能得到$T(n)=O(lo{g}_{2}n)$；

所以这一题的答案为：

• $D.O(lo{g}_{2}n)$；

---

题目2

2.以下算法的时间复杂度为（）

void fun(int n)
{
	int i = 0;
	while (i * i * i <= n)
	{
		i++;
	}
}

$A.O(n)$
$B.O(nlogn)$
$C.O(n^{1/3})$
$D.O(n^{1/2})$

题目解析

这一题也是一个单层循环的题目，下面我们按步骤来对这个循环进行分析；

第一步：问题规模

• 这里的条件语句为$i\ast i\ast i<=n$，此时我们可以得到 $i^3<=n$ ，即$i<=n^{1/3}$；所以这里的问题规模为$n^{1/3}$；

第二步：递进方式

• 通过对象语句和递进语句可知，此时的递进方式是从0开始，每次增加1，当执行t次时，从0变成了t；

第三步：问题规模与执行次数的关系

• 当执行t次后，变量i与$n^{1/3}$相等时，可以得到$t=n^{1/3}$;

第四步：写成反函数

• 此时t的系数已经是1了，所以我们可以得到$t=T(n)=n^{1/3}$；

第五步：改写表达式

• 此时我们在$n^{1/3}$的前面加一个O就能得到$T(n)=O(n^{1/3})$；

所以这一题的答案为：

• $C.O(n^{1/3})$；

---

题目3

3.在下列程序段中，$n$为正整数，则最后一行语句的频度在最坏情况下是（）。

for (i = n - 1; i > 1; i--)
{
	for (j = 1; j < i; j++)
	{
		if (A[j] > A[j + 1])
		{
			A[j]与A[j + 1]对换;//求最坏情况下的语句频度
		}
	}
}

$A.O(n)$
$B.O(nlogn)$
$C.O(n^3)$
$D.O(n^2)$

题目解析

这一题是一个嵌套循环的题目，下面我们按步骤来对这个循环进行分析；

1. 外层循环

1. 问题规模

• 这里相比于我们前面分析的循环，它稍微有些不同，此时的判断语句为i > 1，我们现在无法通过判断语句来确定问题规模，那么我们就需要借助对象语句，看一下此时的起始值是什么，再来进一步确定问题规模；
• 现在的起始值为 $n-1$，那就是这里的最大值为$n-1$，最小值为1，这样我们就可以确定这里的问题规模为$n-1$；

2. 递进方式

• 从递进语句i--; 我们可以得到此时每执行一次，起始值就会减少1，执行t次，起始值就会减少t；

3. 执行次数与问题规模的关系

• 当 $t=n-2$ 时，我们就能得到 $n-1-t=n-1-(n-2)=1$ ;
  也就是说，此时的执行次数与问题规模的关系为 $t=n-2$ ；
  当n的值很大时，此时的2是可以忽略不计的，所以我们就得到了他们的关系式$t=n$；

4. 写成反函数

• 根据他们的关系式，我们可以得到表达式$t=T(n)=n$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(n)$；

2. 内层循环

1. 问题规模

• 根据这里的条件语句j < i; 我们可以得到，这里的问题规模与外层循环的变量 i 是有关系的，外层循环每循环一次就会减少1，那内层循环的问题规模也是每进入一次就减少1；
  也就是说内层循环的问题规模是从$n-1$到 2 ，这里我们就拿最大的问题规模$n-1$来继续分析；

2. 递进方式

• 从对象语句j = 1;和递进语句j++; 我们可以得到，此时每执行一次，起始值就会加1，执行t次，起始值就会加t；

3. 执行次数与问题规模的关系

• 当 $t=n-2$ 时，我们就能得到 $1+t=1+n-2=n-1$ ;
  也就是说，此时的执行次数与问题规模的关系为 $t=n-2$ ；
  此时因为问题规模是在逐渐减小的，所以我们需要保留这个表达式，不能像前面一样省略这个2；

4. 写成反函数

• 根据他们的关系式，我们可以得到表达式$t=T(n)=n-2$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(n-2)$；

3. 合并表达式

现在我们需要分析一下这里合并表达式的方式，具体是通过加法规则进行合并还是通过乘法规则进行合并；

• 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
• 对于这个代码来说，外层循环总共要执行$n-1$次，每执行一次，内层循环就要执行 i 次；
• 因为 i 的值会随着执行次数的增加而减少，所以内层循环的执行次数会依次减少，所以内层循环的总次数应该是：
  $$(n-1)+(n-2)+(n-3)+\dots \dots +3+2$$
• 根据求和公式：$$(首项+尾项)\times 项数/2$$
  我们能够得到最终的表达式$T(n)=(n^2-n-2)/2$；
• 这里我们将表达式的每一项的系数都改为1，并在每一项的前面加上O，就能得到$T(n)=O(n^2)+O(n)+O(1)$；
  所以此时我们需要使用加法规则来进行合并，即$T(n)=O(n^2)+O(n)+O(1)=max(O(n^2),O(n),O(1))=O(n^2)$；

4. 注意事项

• 时间复杂度的分析，我们只需要看最深层循环的时间复杂度就行，这里我们通过求和公式得到的是深层循环需要执行的总次数，即内层循环的执行次数与问题规模之间的关系，它所得到的时间复杂度就可以代表整个代码的时间复杂度了；
• 常数项的时间复杂度的渐近表达式为O(1)，此时不管常数项是多大，1也好，1000000也好，只要是常数项，我们在写成渐近表达式时就可以写成O(1)；

所以这一题的答案为：

• $D.O(n^2)$；

---

题目4

4.以下算法中最后一行语句的执行次数为（）

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= 2 * i; j++)
		{
			m++;
		}
	}`

$A.n(n+1)$
$B.n$
$C.n+1$
$D.n^2$

题目解析

这一题也是一个嵌套循环的题目，这一题与上一题相比，区别不大，我们根据上一题的解题步骤一步一步来分析即可；

1. 外层循环

1. 问题规模

• 我们根据条件语句i <= n; 可以得到，外层循环的问题规模为n；

2. 递进方式

• 从对象语句i = 1; 和递进语句i++; 我们可以得到此时每执行一次，起始值就会增加1，执行t次，起始值就会增加t；

3. 执行次数与问题规模的关系

• 当 $t=n-1$ 时，我们就能得到 $1+t=1+n=n$ ;
  也就是说，此时的执行次数与问题规模的关系为 $t=n-1$ ；
  当n的值很大时，此时的1是可以忽略不计的，所以我们就得到了他们的关系式$t=n$；

4. 写成反函数

• 根据他们的关系式，我们可以得到表达式$t=T(n)=n$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(n)$；

2. 内层循环

1. 问题规模

• 根据这里的条件语句j <= 2 * i; 我们可以得到，这里的问题规模与外层循环的变量 i 是有关系的，外层循环每循环一次就会增加1，那内层循环的问题规模也是每进入一次就会增大到原来的2倍；
  也就是说内层循环的问题规模是从2到$2n$ ，这里我们就拿最大的问题规模$2n$来继续分析；

2. 递进方式

• 从对象语句j = 1;和递进语句j++; 我们可以得到，此时每执行一次，起始值就会加1，执行t次，起始值就会加t；

3. 执行次数与问题规模的关系

• 当 $t=2n-1$ 时，我们就能得到 $1+t=1+2n-1=2n$ ;
  也就是说，此时的执行次数与问题规模的关系为 $t=2n-1$ ；
  此时因为问题规模是在逐渐增加的，所以我们需要保留这个表达式，不能像前面一样省略这个1；

4. 写成反函数

• 根据他们的关系式，我们可以得到表达式$t=T(n)=2n-1$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(2n-1)$；

3. 合并表达式

现在我们需要分析一下这里合并表达式的方式，具体是通过加法规则进行合并还是通过乘法规则进行合并；

• 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
• 对于这个代码来说，外层循环要执行n次，每执行一次，内层循环就要执行n次；
• 这里外层循环总共要执行$n$次，但是内层循环的执行次数会依次增加，所以内层循环的总次数应该是：
  $$2+4+6+\dots \dots +2(n-1)+2n$$
• 根据项数公式：$$(尾项-首项)/项差+1$$
  以及求和公式：$$(首项+尾项)\times 项数/2$$
  我们能够得到最终的表达式$T(n)=n^2+n$；
• 这里我们将表达式的每一项的系数都改为1，并在每一项的前面加上O，就能得到$T(n)=O(n^2)+O(n)$；
  所以此时我们需要使用加法规则来进行合并，即$T(n)=O(n^2)+O(n)=max(O(n^2),O(n))=O(n^2)$；

所以这一题的答案为：

• $A.n(n+1)$；

---

题目5

5.设$n$是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）

	x = 2;
	while (x < n / 2)
	{
		x = 2 * x;
	}

$A.O(lo{g}_{2}n)$
$B.O(n)$
$C.O(nlo{g}_{2}n)$
$D.O(n^2)$

题目解析

这一题是一个单层循环的题目，下面我们按步骤来对这个循环进行分析；

第一步：问题规模

• 通过条件语句可知，这里的问题规模为$n/2$；

第二步：递进方式

• 通过对象语句和递进语句可知，此时的递进方式是从2开始，每次扩大2倍，当执行t次时，就要扩大$2\ast 2\ast 2\ast \dots \dots \ast 2=2^t$倍；

第三步：问题规模与执行次数的关系

• 当执行t次后，变量x与$n/2$相等时，可以得到$2^t=n/2$，这里我们先将两边同时乘以2，得到 $2^{t+1}=n$；

第四步：写成反函数

• $2^{t+1}=n$这个表达式我们需要给等式两边同时取对数，即可得到$t=T(n)=lo{g}_{2}n-1$；

第五步：改写表达式

• 此时我们在$lo{g}_{2}n-1$的每一项前面加一个O就能得到$T(n)=O(lo{g}_{2}n)+O(1)$；
• 根据加法规则我们可以得到$T(n)=O(lo{g}_{2}n)+O(1)=max(O(lo{g}_{2}n),O(1))=O(lo{g}_{2}n)$；

所以这一题的答案为：

• $A.O(lo{g}_{2}n)$；

---

题目6

6.求整数$n(n>=0)$的阶乘算法如下，其时间复杂度为（）

int fact(int n)
{
	if (n <= 1)
	{
		return 1;
	}
	return n * fact(n - 1);
}

$A.O(lo{g}_{2}n)$
$B.O(n)$
$C.O(nlo{g}_{2}n)$
$D.O(n^2)$

题目解析

这一题是一个递归的题目，递归与循环的区别在于对内存的消耗，这个不是我们的重点，我就不展开叙述了，递归与循环的相似之处在于它也是重复的完成一个任务，下面我们就来分析一下它的时间复杂度；

第一步：问题规模

• 通过条件语句可知，这里的递归是从n到1，也就是说递归的问题规模就是n；

第二步：递进方式

• 通过递归的传参return n * fact(n - 1); 这里的$n-1$可知，它的递进方式是每次递进时，n的值会减少1，递进t次，n值会减少t；

第三步：问题规模与执行次数的关系

• 当执行t次后，n的值变为1，此时就会开始回归，我们需要找到的是n变为1的过程，也就是执行t次后n值与t的关系$n-t=1$;
  我们可以很容易的得到$n=t+1$；

第四步：写成反函数

• $n=t+1$这个表达式我们只需要简单的进行移项就能得到$t=T(n)=n-1$；

第五步：改写表达式

• 此时我们将$n-1$的每一项系数改成1并在每一项前面加一个O就能得到$T(n)=O(n)+O(1)$；
  根据加法规则可以得到时间复杂度的渐近表达式：$T(n)=O(n)+O(1)=max(O(n),O(1))=O(n)$

所以这一题的答案为：

• $B.O(n)$；

---

题目7

7.以下程序段的时间复杂度为（）

	count = 0;
	for (k = 1; k <= n; k *= 2)
	{
		for (j = 1; j <= n; j++)
		{
			count++;
		}
	}

$A.O(lo{g}_{2}n)$
$B.O(n)$
$C.O(nlo{g}_{2}n)$
$D.O(n^2)$

题目解析

这一题也是一个嵌套循环的题目，这里的嵌套循环与我们前面做的相比，要稍微简单一点，它更加贴近我们在讲解思路时用的嵌套循环的例子；

1. 外层循环

1. 问题规模

• 我们根据条件语句k <= n; 可以得到，外层循环的问题规模为n；

2. 递进方式

• 从对象语句k = 1; 和递进语句k *= 2; 我们可以得到此时每执行一次，起始值就会变为原来的2倍，执行t次，起始值就会变为原来的$2^t$倍；

3. 执行次数与问题规模的关系

• 当执行t次后时，变量k与问题规模n的值相等，那我们就能得到 $2^t=n$ ;
  也就是说，此时的执行次数与问题规模的关系为 $2^t=n$ ；

4. 写成反函数

• 根据他们的关系式，我们在等式两边同时取对数，就可以得到表达式$t=T(n)=lo{g}_{2}n$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(lo{g}_{2}n)$；

2. 内层循环

1. 问题规模

• 根据这里的条件语句j <= n; 我们可以得到，这里的问题规模与外层循环一样，也是n；；

2. 递进方式

• 从对象语句j = 1;和递进语句j++; 我们可以得到，此时每执行一次，起始值就会加1，执行t次，起始值就会加t；

3. 执行次数与问题规模的关系

• 当 $t=n-1$ 时，我们就能得到 $1+t=1+n-1=n$ ;
  也就是说，此时的执行次数与问题规模的关系为 $t=n-1$ ；
  此时当n的值足够大时，这个1是可以忽略不计的，所以我们可以直接把它省略掉，那我们就得到了表达式$t=n$；

4. 写成反函数

• 根据他们的关系式，我们可以得到表达式$t=T(n)=n$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(n)$；

3. 合并表达式

现在我们需要分析一下这里合并表达式的方式，具体是通过加法规则进行合并还是通过乘法规则进行合并；

• 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
• 对于这个代码来说，外层循环要执行n次，每执行一次，内层循环就要执行n次；
• 这里外层循环总共要执行$lo{g}_{2}n$次，所以内层循环的总次数应该是：
  $$n+n+n+\dots \dots +n=n\ast lo{g}_{2}n$$
  我们能够得到最终的表达式$T(n)=n\ast lo{g}_{2}n$；
• 这里我们将$n\ast lo{g}_{2}n$的前面加上O，就能得到$T(n)=O(n\ast lo{g}_{2}n)$；

所以这一题的答案为：

• $C.O(nlo{g}_{2}n)$；

---

题目8

8.下列函数的时间复杂度为（）

int func(int n)
{
	int i = 0, sum = 0;
	while (sum < n)
	{
		sum += ++i;
	}
	return i;
}

$A.O(logn)$
$B.O(n^{1/2})$
$C.O(n)$
$D.O(nlogn)$

题目解析

这一题是一个单层循环的题目，现在大家对单层循环的题应该都是有感觉了，下面我们直接来进行分析；

第一步：问题规模

• 通过条件语句可知，这里的问题规模为n；

第二步：递进方式

• 通过对象语句和递进语句可知，此时的递进方式是从0开始，每次增加i，这里需要注意，此时增加的值为i，我们来看一下i是如何变化的；
• 通过++i; 可知，i的值是先加1，再使用，也就是执行一次时，sum的值加1，执行2次时，sum的值加2，执行t此时，sum的值加t；

第三步：问题规模与执行次数的关系

• 当执行t次后，变量sum与n相等时，可以得到$1+2+3+\dots \dots +t=n$;
• 根据项数公式：$$(尾项-首项)/项差+1$$
  以及求和公式：$$(首项+尾项)\times 项数/2$$
  我们能够得到最终的表达式$(t^2+t)/2=n$；

第四步：写成反函数

• $(t^2+t)/2=n$这个表达式我们先将表达式改写成$t^2+2\ast (1/2)\ast t=2n$，此时我们就可以很容易得到$(t+1/2{)}^2=2n+1/4$；
  之后我们在进行开方移项，即可得到$t=T(n)=(2n+1/4{)}^{1/2}-1/2$；

第五步：改写表达式

• 此时我们将 $(2n+1/4{)}^{1/2}-1/2$ 每一项的系数改为1，并在前面加一个O就能得到$T(n)=O((2n+1/4{)}^{1/2})+O(1)$；
  根据加法规则，我们可很容易的得到$T(n)=O((2n+1/4{)}^{1/2})$；
  此时当n足够大时，这里的1/4是可以忽略不计的，所以我们可以得到表达式：$T(n)=O((2n{)}^{1/2})$；
  此时再将n的系数改为1，就能得到我们最终的时间复杂度的渐近表达式：$T(n)=O(n^{1/2})$；

所以这一题的答案为：

• $B.O(n^{1/2})$；

---

题目9

9.设$n$是描述问题规模的非负整数，以下程序段的时间复杂度为（）

x = 0;
while (n >= (x + 1) * (x + 1))
{
	x = x + 1;
}

$A.O(logn)$
$B.O(n^{1/2})$
$C.O(n)$
$D.O(n^2)$

题目解析

这一题又是一个单层循环的题目，下面我们直接来分析；

第一步：问题规模

• 这里的条件语句n >= (x + 1) * (x + 1) 我们需要先将其改写一下，得到表达式$x<=n^{1/2}-1$；
  现在我们就能得到问题规模为：$n^{1/2}-1$；

第二步：递进方式

• 通过对象语句和递进语句可知，此时的递进方式是从0开始，每次增加1，当执行t次时，就要增加t；

第三步：问题规模与执行次数的关系

• 当执行t次后，变量x与$n^{1/2}-1$相等时，可以得到 $t=n^{1/2}-1$;

第四步：写成反函数

• $t=n^{1/2}-1$这个表达式已经是t与n的关系表达式了，所以我们将其改写一下即可得到$t=T(n)=n^{1/2}-1$；
  当然这里的1也是可以省略的，即使这里不省略，在后面改写表达式时根据加法规则也会将其省略掉；

第五步：改写表达式

• 此时我们将$n^{1/2}-1$的每一项的系数改为1，并在前面加一个O就能得到$T(n)=O(n^{1/2})+O(1)$；
  根据加法规则我们就能得到$T(n)=O(n^{1/2})$；

所以这一题的答案为：

• $B.O(n^{1/2})$；

---

题目10

10.以下程序段的时间复杂度为（）

int sum = 0;
for (int i = 1; i < n; i *= 2)
{
	for (int j = 0; j < i; j++)
	{
		sum++;
	}
}

$A.O(logn)$
$B.O(n)$
$C.O(nlogn)$
$D.O(n^2)$

题目解析

这一题是一个嵌套循环的题目，看到题目，是不是感觉和上面做的第三题和第四题有点像啊，下面我们来直接进行分析；

1. 外层循环

1. 问题规模

• 根据条件语句我们可以很容易的得到外层循环的问题规模为n

2. 递进方式

• 从对象语句int i = 1; 和递进语句i *= 2; 我们可以得到，此时每执行一次，起始值就扩大为原来的2倍，执行t次，起始值就会扩大为$2^t$；

3. 执行次数与问题规模的关系

• 当执行t次时，变量 i 与问题规模 n 相等，我们就能得到 $2^t=n$ ;

4. 写成反函数

• 根据他们的关系式，将等式两边同时取对数，我们可以得到表达式$t=T(n)=lo{g}_{2}n$ ；

5. 改写表达式

• 在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 $T(n)=O(lo{g}_{2}n)$；

2. 内层循环

1. 问题规模

• 根据这里的条件语句j < i; 我们可以得到，这里的问题规模与外层循环的变量 i 是有关系的，外层循环每循环一次就会扩大为原来的2倍，那内层循环的问题规模也是每进入一次就扩大为原来的2倍；
  也就是说内层循环的问题规模是从1到$2n$ ，这里我们就拿最大的问题规模$2n$来继续分析；

2. 递进方式

• 从对象语句j = 0;和递进语句j++; 我们可以得到，此时每执行一次，起始值就会加1，执行t次，起始值就会加t；

3. 执行次数与问题规模的关系

• 当执行t次时，变量 j 与问题规模 2n 相等，我们就能得到 $t=2n$ ;

4. 写成反函数

• 根据他们的关系式，我们可以得到表达式$t=T(n)=2n$ ；

5. 改写表达式

• 在得到表达式之后，我们将n的系数改为1，并加上O就能得到时间复杂度的渐近表达式 $T(n)=O(n)$；

3. 合并表达式

现在我们需要分析一下这里合并表达式的方式，具体是通过加法规则进行合并还是通过乘法规则进行合并；

• 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。

• 对于这个代码来说，外层循环要执行$lo{g}_{2}n$次，每执行一次，内层循环就要执行 i 次；

• 因为 i 的值会随着循环次数的增加而增加，所以内层循环的执行次数会也会随着 i 值的增加而增加，所以内层循环的总次数应该是：
  $$1+2+4+8+\dots \dots +2n$$
  根据等比数列求和公式：$$首项\times (公{比}^n-1)/(公比-1)=a_1\times (q^n-1)/(q-1)$$
  我们能够得到最终的表达式$t=1\ast (2^{lo{g}_{2}n}-1)/(2-1)=n-1$

• 这里我们将表达式的系数改为1，并在每一项前面加上O，就能得到$T(n)=O(n)+O(1)$；
  根据加法规则我们可以得到：$T(n)=O(n)+O(1)=max(O(n),O(1))=O(n)$；

所以这一题的答案为：

• $B.O(n)$；

结语

第一章的内容现在我们就全部介绍完了，不知道大家在看完这篇内容后，对时间复杂度的求解还有没有什么问题，这里有个投票大家可以参与一下，我会根据投票情况来决定需不需要再出一篇这个内容，希望大家能够踊跃参与。

接下来，我们将开始进入第二章的内容——线性表。从这个篇章开始，咱们需要有指针和结构体等C语言的基本功，这样才能更好的理解这些内容。为了帮助大家更好的理解，我也会在【C语言必学知识点】专栏中介绍这些知识点，大家记得关注哦！

最后感谢大家的翻阅，咱们下一篇再见！！！

【数据结构】第一章——绪论

【数据结构】第一章——绪论（1）：【数据结构的基本概念】

• 本章内容介绍了数据结构的基本概念和术语以及数据结构的三要素

【数据结构】第一章——绪论（2）：【算法】

• 本章介绍了算法的基本概念

【数据结构】第一章——绪论（3）：【时间复杂度】

• 本章详细介绍了算法的时间复杂度

【数据结构】第一章——绪论（4）：【空间复杂度】

• 本章详细介绍了算法的空间复杂度