首页 > 其他分享 >【数据结构】第一章——习题演练

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

时间：2023-12-02 13:32:21浏览次数：36  
标签：语句 执行 复杂度 递进 循环 习题 数据结构 演练 表达式

【数据结构】第一章——习题演练_嵌套循环

导言

本篇章题目出自：王道考研系列丛书——《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；

  • 第四步：写成反函数

在得到执行次数与问题规模之间的关系表达式之后，我们就需要找到表达式的反函数，并将其改写成【数据结构】第一章——习题演练_条件语句_02的形式。

改写的方式很简单，我们只需要将执行次数 t 的系数变为1就行。

比如这里的【数据结构】第一章——习题演练_条件语句_03，此时 t 的系数就已经是1了，所以我们可以直接写成【数据结构】第一章——习题演练_嵌套循环_04；

  • 第五步：改写表达式

在得到执行次数 t 关于问题规模 n 的表达式之后，我们只需要在问题规模这一侧在n的前面加一个【数据结构】第一章——习题演练_嵌套循环_05；

此时我们就能得到【数据结构】第一章——习题演练_时间复杂度_06；

嵌套循环

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

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

外层循环

  1. 问题规模
  • 通过判断语句可知，外层循环的问题规模为n；
  1. 递进方式
  • 通过对象语句和递进语句可知，外层循环的递进方式是从0开始每次增加1；
  1. 执行次数与问题规模的关系
  • 由递进方式可知，当执行t次时，变量 i 就会从0变成 t ，当t = n时，就可以得到它们之间的关系为t = n；
  1. 写成反函数
  • 因为此时t的系数已经为1，所以我们可以很容易得到表达式 【数据结构】第一章——习题演练_嵌套循环_04；
  1. 改写表达式
  • 现在我们只需要在 n 前面加一个O就可以得到时间复杂度的表达式了，即【数据结构】第一章——习题演练_时间复杂度_06；


内层循环

  1. 问题规模
  • 通过判断语句可知，内层循环的问题规模为n；
  1. 递进方式
  • 通过对象语句和递进语句可知，内层循环的递进方式是从0开始每次增加1；
  1. 执行次数与问题规模的关系
  • 由递进方式可知，当执行t次时，变量 i 就会从0变成 t ，当t = n时，就可以得到它们之间的关系为t = n；
  1. 写成反函数
  • 因为此时t的系数已经为1，所以我们可以很容易得到表达式 【数据结构】第一章——习题演练_嵌套循环_04；
  1. 改写表达式
  • 现在我们只需要在 n 前面加一个O就可以得到时间复杂度的表达式了，即【数据结构】第一章——习题演练_时间复杂度_06；


合并表达式

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

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

对于这个代码来说，外层循环要执行n次，每执行一次，内层循环就要执行n次，

即外层循环执行n次，内层循环就要执行n+n+n+……+n=n*n次；

所以此时我们需要使用乘法规则来进行合并，即【数据结构】第一章——习题演练_条件语句_11；

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

单项选择题

题目1

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

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

【数据结构】第一章——习题演练_条件语句_12 【数据结构】第一章——习题演练_嵌套循环_13 【数据结构】第一章——习题演练_条件语句_14 【数据结构】第一章——习题演练_时间复杂度_15

题目解析

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

第一步：问题规模

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

第二步：递进方式

  • 通过对象语句int i = 1;和递进语句i = i * 2;可知，此时的递进方式是从1开始，每次扩大2倍；当执行t次时，就要扩大【数据结构】第一章——习题演练_条件语句_16倍；

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

  • 当执行t次后，变量i与n相等时，可以得到【数据结构】第一章——习题演练_条件语句_17;

第四步：写成反函数

  • 【数据结构】第一章——习题演练_条件语句_17这个表达式我们需要给等式两边同时取对数，即可得到【数据结构】第一章——习题演练_嵌套循环_19；

第五步：改写表达式

  • 此时我们在【数据结构】第一章——习题演练_时间复杂度_20的前面加一个O就能得到【数据结构】第一章——习题演练_时间复杂度_21；

所以这一题的答案为：

 【数据结构】第一章——习题演练_时间复杂度_15；

题目2

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

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

【数据结构】第一章——习题演练_条件语句_12 【数据结构】第一章——习题演练_时间复杂度_24 【数据结构】第一章——习题演练_嵌套循环_25 【数据结构】第一章——习题演练_时间复杂度_26

题目解析

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

第一步：问题规模

  • 这里的条件语句为【数据结构】第一章——习题演练_时间复杂度_27，此时我们可以得到 【数据结构】第一章——习题演练_嵌套循环_28 ，即【数据结构】第一章——习题演练_条件语句_29；所以这里的问题规模为【数据结构】第一章——习题演练_时间复杂度_30；

第二步：递进方式

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

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

  • 当执行t次后，变量i与【数据结构】第一章——习题演练_时间复杂度_30相等时，可以得到【数据结构】第一章——习题演练_条件语句_32;

第四步：写成反函数

  • 此时t的系数已经是1了，所以我们可以得到【数据结构】第一章——习题演练_嵌套循环_33；

第五步：改写表达式

  • 此时我们在【数据结构】第一章——习题演练_时间复杂度_30的前面加一个O就能得到【数据结构】第一章——习题演练_嵌套循环_35；

所以这一题的答案为：

【数据结构】第一章——习题演练_嵌套循环_25；

题目3

3.在下列程序段中，【数据结构】第一章——习题演练_时间复杂度_37为正整数，则最后一行语句的频度在最坏情况下是（）。

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

【数据结构】第一章——习题演练_条件语句_12 【数据结构】第一章——习题演练_时间复杂度_24 【数据结构】第一章——习题演练_嵌套循环_40 【数据结构】第一章——习题演练_时间复杂度_41

题目解析

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

  • 外层循环
  1. 问题规模

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

现在的起始值为 【数据结构】第一章——习题演练_时间复杂度_42，那就是这里的最大值为【数据结构】第一章——习题演练_时间复杂度_42，最小值为1，这样我们就可以确定这里的问题规模为【数据结构】第一章——习题演练_时间复杂度_42；

  1. 递进方式

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

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

当 【数据结构】第一章——习题演练_条件语句_45 时，我们就能得到【数据结构】第一章——习题演练_时间复杂度_46 ;

也就是说，此时的执行次数与问题规模的关系为 【数据结构】第一章——习题演练_条件语句_45 ；

当n的值很大时，此时的2是可以忽略不计的，所以我们就得到了他们的关系式【数据结构】第一章——习题演练_条件语句_03；

  1. 写成反函数

根据他们的关系式，我们可以得到表达式【数据结构】第一章——习题演练_嵌套循环_04；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_06；

  • 内层循环
  1. 问题规模

根据这里的条件语句j < i; 我们可以得到，这里的问题规模与外层循环的变量 i 是有关系的;

外层循环每循环一次就会减少1，那内层循环的问题规模也是每进入一次就减少1；

也就是说内层循环的问题规模是从【数据结构】第一章——习题演练_条件语句_51到 2 ，这里我们就拿最大的问题规模【数据结构】第一章——习题演练_条件语句_51来继续分析；

  1. 递进方式

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

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

当 【数据结构】第一章——习题演练_条件语句_45 时，我们就能得到 【数据结构】第一章——习题演练_时间复杂度_54 ;

也就是说，此时的执行次数与问题规模的关系为 【数据结构】第一章——习题演练_条件语句_45 ；

此时因为问题规模是在逐渐减小的，所以我们需要保留这个表达式，不能像前面一样省略这个2；

  1. 写成反函数

根据他们的关系式，我们可以得到表达式【数据结构】第一章——习题演练_时间复杂度_56 ；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_57；

  • 合并表达式

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

  • 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
  • 对于这个代码来说，外层循环总共要执行

因为 i 的值会随着执行次数的增加而减少，所以内层循环的执行次数会依次减少，

  • 所以内层循环的总次数应该是：

【数据结构】第一章——习题演练_时间复杂度_58

  • 根据求和公式：

 【数据结构】第一章——习题演练_条件语句_59

我们能够得到最终的表达式【数据结构】第一章——习题演练_时间复杂度_60；

这里我们将表达式的每一项的系数都改为1，并在每一项的前面加上O，就能得到【数据结构】第一章——习题演练_时间复杂度_61；

所以此时我们需要使用加法规则来进行合并，即【数据结构】第一章——习题演练_时间复杂度_62；

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

所以这一题的答案为：

【数据结构】第一章——习题演练_时间复杂度_41；

题目4

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

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

【数据结构】第一章——习题演练_条件语句_64 【数据结构】第一章——习题演练_条件语句_65 【数据结构】第一章——习题演练_嵌套循环_66 【数据结构】第一章——习题演练_条件语句_67

题目解析

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

  • 外层循环
  1. 问题规模

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

  1. 递进方式

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

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

当 【数据结构】第一章——习题演练_嵌套循环_68 时，我们就能得到 【数据结构】第一章——习题演练_嵌套循环_69 ;

也就是说，此时的执行次数与问题规模的关系为 【数据结构】第一章——习题演练_嵌套循环_68 ；

当n的值很大时，此时的1是可以忽略不计的，所以我们就得到了他们的关系式【数据结构】第一章——习题演练_条件语句_03；

  1. 写成反函数

根据他们的关系式，我们可以得到表达式【数据结构】第一章——习题演练_嵌套循环_04 ；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_06；

  • 内层循环
  1. 问题规模

根据这里的条件语句j <= 2 * i; 我们可以得到，这里的问题规模与外层循环的变量 i 是有关系的;

外层循环每循环一次就会增加1，那内层循环的问题规模也是每进入一次就会增大到原来的2倍；

也就是说内层循环的问题规模是从2到【数据结构】第一章——习题演练_条件语句_74 ，这里我们就拿最大的问题规模【数据结构】第一章——习题演练_条件语句_74来继续分析；

  1. 递进方式

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

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

当 【数据结构】第一章——习题演练_条件语句_76 时，我们就能得到 【数据结构】第一章——习题演练_时间复杂度_77 ;

也就是说，此时的执行次数与问题规模的关系为 【数据结构】第一章——习题演练_条件语句_76 ；

此时因为问题规模是在逐渐增加的，所以我们需要保留这个表达式，不能像前面一样省略这个1；

  1. 写成反函数

根据他们的关系式，我们可以得到表达式【数据结构】第一章——习题演练_条件语句_79 ；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_80；

  • 合并表达式

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

  • 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
  • 对于这个代码来说，外层循环要执行n次，每执行一次，内层循环就要执行n次；
  • 这里外层循环总共要执行【数据结构】第一章——习题演练_时间复杂度_37次，但是内层循环的执行次数会依次增加，所以内层循环的总次数应该是：

【数据结构】第一章——习题演练_时间复杂度_82

  • 根据项数公式：

【数据结构】第一章——习题演练_时间复杂度_83

  • 以及求和公式：

【数据结构】第一章——习题演练_条件语句_59

我们能够得到最终的表达式【数据结构】第一章——习题演练_嵌套循环_85；

这里我们将表达式的每一项的系数都改为1，并在每一项的前面加上O，就能得到【数据结构】第一章——习题演练_嵌套循环_86；

所以此时我们需要使用加法规则来进行合并，即【数据结构】第一章——习题演练_条件语句_87；

所以这一题的答案为：

【数据结构】第一章——习题演练_条件语句_64；

题目5

5.设【数据结构】第一章——习题演练_时间复杂度_37是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）

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

【数据结构】第一章——习题演练_嵌套循环_90 【数据结构】第一章——习题演练_嵌套循环_91 【数据结构】第一章——习题演练_条件语句_14 【数据结构】第一章——习题演练_时间复杂度_41

题目解析

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

  • 第一步：问题规模

通过条件语句可知，这里的问题规模为【数据结构】第一章——习题演练_嵌套循环_94；

  • 第二步：递进方式

通过对象语句和递进语句可知，此时的递进方式是从2开始，每次扩大2倍；

当执行t次时，就要扩大【数据结构】第一章——习题演练_条件语句_16倍；

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

当执行t次后，变量x与【数据结构】第一章——习题演练_嵌套循环_94相等时，可以得到【数据结构】第一章——习题演练_时间复杂度_97，这里我们先将两边同时乘以2，得到 【数据结构】第一章——习题演练_条件语句_98；

  • 第四步：写成反函数

【数据结构】第一章——习题演练_条件语句_98这个表达式我们需要给等式两边同时取对数，即可得到【数据结构】第一章——习题演练_嵌套循环_100；

  • 第五步：改写表达式

此时我们在【数据结构】第一章——习题演练_条件语句_101的每一项前面加一个O就能得到【数据结构】第一章——习题演练_条件语句_102；

根据加法规则我们可以得到【数据结构】第一章——习题演练_时间复杂度_103；

所以这一题的答案为：

【数据结构】第一章——习题演练_嵌套循环_90；

题目6

6.求整数【数据结构】第一章——习题演练_条件语句_105的阶乘算法如下，其时间复杂度为（）

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

【数据结构】第一章——习题演练_嵌套循环_90 【数据结构】第一章——习题演练_嵌套循环_91 【数据结构】第一章——习题演练_条件语句_14 【数据结构】第一章——习题演练_时间复杂度_41

题目解析

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

  • 第一步：问题规模

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

  • 第二步：递进方式

通过递归的传参return n * fact(n - 1); 这里的【数据结构】第一章——习题演练_条件语句_51可知，

它的递进方式是每次递进时，n的值会减少1，递进t次，n值会减少t；

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

当执行t次后，n的值变为1，此时就会开始回归，我们需要找到的是n变为1的过程;

也就是执行t次后n值与t的关系【数据结构】第一章——习题演练_条件语句_111; 我们可以很容易的得到【数据结构】第一章——习题演练_嵌套循环_112；

  • 第四步：写成反函数

【数据结构】第一章——习题演练_嵌套循环_112这个表达式我们只需要简单的进行移项就能得到【数据结构】第一章——习题演练_嵌套循环_114；

  • 第五步：改写表达式

此时我们将【数据结构】第一章——习题演练_条件语句_51的每一项系数改成1并在每一项前面加一个O就能得到【数据结构】第一章——习题演练_嵌套循环_116；

根据加法规则可以得到时间复杂度的渐近表达式：【数据结构】第一章——习题演练_条件语句_117

所以这一题的答案为：

【数据结构】第一章——习题演练_嵌套循环_91；

题目7

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

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

【数据结构】第一章——习题演练_嵌套循环_90 【数据结构】第一章——习题演练_嵌套循环_91 【数据结构】第一章——习题演练_条件语句_14 【数据结构】第一章——习题演练_时间复杂度_41

题目解析

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

  • 外层循环
  1. 问题规模

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

  1. 递进方式

从对象语句k = 1; 和递进语句k *= 2; 我们可以得到：

此时每执行一次，起始值就会变为原来的2倍，执行t次，起始值就会变为原来的【数据结构】第一章——习题演练_嵌套循环_123倍；

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

当执行t次后时，变量k与问题规模n的值相等，那我们就能得到 【数据结构】第一章——习题演练_条件语句_17 ;

也就是说，此时的执行次数与问题规模的关系为 【数据结构】第一章——习题演练_条件语句_17 ；

  1. 写成反函数

根据他们的关系式，我们在等式两边同时取对数，就可以得到表达式【数据结构】第一章——习题演练_嵌套循环_19 ；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_21；

  • 内层循环
  1. 问题规模

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

  1. 递进方式

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

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

当 【数据结构】第一章——习题演练_嵌套循环_68 时，我们就能得到 【数据结构】第一章——习题演练_条件语句_129 ;

也就是说，此时的执行次数与问题规模的关系为 【数据结构】第一章——习题演练_嵌套循环_68 ；

此时当n的值足够大时，这个1是可以忽略不计的，所以我们可以直接把它省略掉，那我们就得到了表达式【数据结构】第一章——习题演练_条件语句_03；

  1. 写成反函数

根据他们的关系式，我们可以得到表达式【数据结构】第一章——习题演练_嵌套循环_04 ；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_06；

  • 合并表达式

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

  • 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
  • 对于这个代码来说，外层循环要执行n次，每执行一次，内层循环就要执行n次；
  • 这里外层循环总共要执行【数据结构】第一章——习题演练_时间复杂度_20次，所以内层循环的总次数应该是：

【数据结构】第一章——习题演练_条件语句_135

我们能够得到最终的表达式【数据结构】第一章——习题演练_时间复杂度_136；

  • 这里我们将【数据结构】第一章——习题演练_嵌套循环_137的前面加上O，就能得到【数据结构】第一章——习题演练_时间复杂度_138；

所以这一题的答案为：

【数据结构】第一章——习题演练_条件语句_14；

题目8

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

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

【数据结构】第一章——习题演练_时间复杂度_140 【数据结构】第一章——习题演练_时间复杂度_141 【数据结构】第一章——习题演练_条件语句_142 【数据结构】第一章——习题演练_嵌套循环_143

题目解析

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

  • 第一步：问题规模

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

  • 第二步：递进方式

通过对象语句和递进语句可知，此时的递进方式是从0开始，每次增加i；

这里需要注意，此时增加的值为i，我们来看一下i是如何变化的；

通过++i; 可知，i的值是先加1，再使用；

也就是执行一次时，sum的值加1，执行2次时，sum的值加2，执行t此时，sum的值加t；

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

当执行t次后，变量sum与n相等时，可以得到【数据结构】第一章——习题演练_条件语句_144;

根据项数公式：

【数据结构】第一章——习题演练_时间复杂度_83

以及求和公式：

【数据结构】第一章——习题演练_条件语句_59

我们能够得到最终的表达式【数据结构】第一章——习题演练_嵌套循环_147；

  • 第四步：写成反函数

【数据结构】第一章——习题演练_嵌套循环_147这个表达式我们先将表达式改写成【数据结构】第一章——习题演练_条件语句_149，此时我们就可以很容易得到【数据结构】第一章——习题演练_时间复杂度_150；

之后我们在进行开方移项，即可得到【数据结构】第一章——习题演练_嵌套循环_151；

  • 第五步：改写表达式

此时我们将 【数据结构】第一章——习题演练_条件语句_152 每一项的系数改为1，并在前面加一个O就能得到【数据结构】第一章——习题演练_条件语句_153；

根据加法规则，我们可很容易的得到【数据结构】第一章——习题演练_条件语句_154；

此时当n足够大时，这里的1/4是可以忽略不计的，所以我们可以得到表达式：【数据结构】第一章——习题演练_嵌套循环_155；

此时再将n的系数改为1，就能得到我们最终的时间复杂度的渐近表达式：【数据结构】第一章——习题演练_条件语句_156；


所以这一题的答案为：

【数据结构】第一章——习题演练_时间复杂度_141；

题目9

9.设【数据结构】第一章——习题演练_时间复杂度_37是描述问题规模的非负整数，以下程序段的时间复杂度为（）

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

【数据结构】第一章——习题演练_时间复杂度_140 【数据结构】第一章——习题演练_时间复杂度_141 【数据结构】第一章——习题演练_条件语句_142 【数据结构】第一章——习题演练_时间复杂度_41

题目解析

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

  • 第一步：问题规模

这里的条件语句n >= (x + 1) * (x + 1) 我们需要先将其改写一下，得到表达式【数据结构】第一章——习题演练_条件语句_163；

现在我们就能得到问题规模为：【数据结构】第一章——习题演练_条件语句_164；

  • 第二步：递进方式

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

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

当执行t次后，变量x与【数据结构】第一章——习题演练_条件语句_164相等时，可以得到 【数据结构】第一章——习题演练_嵌套循环_166;

  • 第四步：写成反函数

【数据结构】第一章——习题演练_嵌套循环_166这个表达式已经是t与n的关系表达式了，所以我们将其改写一下即可得到【数据结构】第一章——习题演练_时间复杂度_168；

当然这里的1也是可以省略的，即使这里不省略，在后面改写表达式时根据加法规则也会将其省略掉；

  • 第五步：改写表达式

此时我们将【数据结构】第一章——习题演练_条件语句_164的每一项的系数改为1，并在前面加一个O就能得到【数据结构】第一章——习题演练_条件语句_170；

根据加法规则我们就能得到【数据结构】第一章——习题演练_条件语句_156；

所以这一题的答案为：

【数据结构】第一章——习题演练_时间复杂度_141；

题目10

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

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

【数据结构】第一章——习题演练_时间复杂度_140 【数据结构】第一章——习题演练_嵌套循环_91 【数据结构】第一章——习题演练_嵌套循环_175 【数据结构】第一章——习题演练_时间复杂度_41

题目解析

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

  • 外层循环
  1. 问题规模

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

  1. 递进方式

从对象语句int i = 1; 和递进语句i *= 2; 我们可以得到，此时每执行一次，起始值就扩大为原来的2倍，执行t次，起始值就会扩大为【数据结构】第一章——习题演练_嵌套循环_123；

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

当执行t次时，变量 i 与问题规模 n 相等，我们就能得到 【数据结构】第一章——习题演练_条件语句_17 ;

  1. 写成反函数

根据他们的关系式，将等式两边同时取对数，我们可以得到表达式【数据结构】第一章——习题演练_嵌套循环_19 ；

  1. 改写表达式

在得到表达式之后，我们在右侧加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_21；

  • 内层循环
  1. 问题规模

根据这里的条件语句j < i; 我们可以得到，这里的问题规模与外层循环的变量 i 是有关系的;

外层循环每循环一次就会扩大为原来的2倍，那内层循环的问题规模也是每进入一次就扩大为原来的2倍；

也就是说内层循环的问题规模是从1到【数据结构】第一章——习题演练_条件语句_74 ，这里我们就拿最大的问题规模【数据结构】第一章——习题演练_条件语句_74来继续分析；

  1. 递进方式

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

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

当执行t次时，变量 j 与问题规模 2n 相等，我们就能得到 【数据结构】第一章——习题演练_嵌套循环_183 ;

  1. 写成反函数

根据他们的关系式，我们可以得到表达式【数据结构】第一章——习题演练_嵌套循环_184 ；

  1. 改写表达式

在得到表达式之后，我们将n的系数改为1，并加上O就能得到时间复杂度的渐近表达式 【数据结构】第一章——习题演练_时间复杂度_06；

  • 合并表达式

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

  • 嵌套循环的规则是最外层循环执行一次，内层循环要走完整个循环流程。
  • 对于这个代码来说，外层循环要执行【数据结构】第一章——习题演练_时间复杂度_20次，每执行一次，内层循环就要执行 i 次；

因为 i 的值会随着循环次数的增加而增加，所以内层循环的执行次数会也会随着 i 值的增加而增加；

  • 所以内层循环的总次数应该是：

【数据结构】第一章——习题演练_条件语句_187

  • 根据等比数列求和公式：

【数据结构】第一章——习题演练_条件语句_188

我们能够得到最终的表达式: 【数据结构】第一章——习题演练_条件语句_189

这里我们将表达式的系数改为1，并在每一项前面加上O，就能得到【数据结构】第一章——习题演练_嵌套循环_116；

根据加法规则我们可以得到：【数据结构】第一章——习题演练_条件语句_191；

所以这一题的答案为：

【数据结构】第一章——习题演练_嵌套循环_91；

结语

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

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

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

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

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

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

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

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

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

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

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

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

标签：语句,执行,复杂度,递进,循环,习题,数据结构,演练,表达式
From： https://blog.51cto.com/u_16231477/8655274

相关文章

  • 51k+ Star！动画图解、一键运行的数据结构与算法教程！
    大家好，我是Java陈序员。我们都知道，《数据结构与算法》——是程序员的必修课。无论是使用什么编程语音，亦或者是前后端开发，都需要修好《数据结构与算法》这门课！在各个互联网大产的面试中，对数据结构和算法的考核乐此不疲。往往《数据结构与算法》学得好的，都能拿到高薪！但是《数......
  • 数据结构与算法之单链表-----黑马程序员(26-35)
    1.链表的概念在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素储存上并不连续。 创建链表如图所示和相关代码publicclassdanlianbiao{privateNodehead=null;//头部第一个结点privatestaticclassNode{//后面的每个结点intvalue;Nodene......
  • PTA|C语言|数组练习题
    --------------------------------------------------------------------------------求最大值及其下标本题要求编写程序，找出给定的n个数中的最大值及其对应的最小下标（下标从0开始）。输入格式:输入在第一行中给出一个正整数n（1<n≤10）。第二行输入n个整数，用空格分开。输出格式:在一行......
  • 钓鱼邮件演练：多种钓鱼场景及应对策略
    在当今数字化年代，网络垂钓进犯已成为一种常见的安全要挟。为了进步职工对垂钓邮件的辨认才能和防备认识，企业通常会进行垂钓邮件演练。本文将具体剖析多种垂钓演练场景，包含仿冒邮件、链接垂钓邮件和BEC垂钓邮件（商务欺诈）等，协助咱们深化了解网络保安措施。一、仿冒邮件定义与意图......
  • 【数据结构】第一章——绪论（4）
    前言大家好！很高兴又和大家见面啦！！！在上一篇内容中我们重点介绍了时间复杂度，今天我们要介绍的是算法的另一个目标——低存储量需求，也就是算法的空间复杂度。下面我们就来了解一下什么是空间复杂度吧！空间复杂度1.定义算法的空间复杂度为算法所消耗的存储空间，它是问题规模的函数。记为：2.......
  • 汇编-数据结构
      .386.modelflat,stdcalloptioncasemap:none.stack4096includewindows.incExitProcessPROTO,dwExitCode:DWORDSTUDENTstruct;自定义数据结构nameDWORD?IDDWORD?STUDENTends.datastwndclassWNDCLASS<>;末初始化st......
  • 数据结构与算法分析（荣政）953 指定教材
    前言953官方指定教材数据结构与算法分析（荣政）绪论数据元素是数据的基本单位数据项是数据的最小单位数据结构：二元组（D，R），D是数据，R是关系，可考判断题，混淆D和R的含义数据结构包含三部分逻辑结构存储结构在逻辑和存储结构上进行的操作抽象数据类型包含三部分逻辑结构：线性和......
  • Golang-常见数据结构实现原理
    chan 1.chan数据结构 src/runtime/chan.go:hchan定义了channel的数据结构：typehchanstruct{qcountuint//当前队列中剩余元素个数dataqsizuint//环形队列长度，即可以存放的元素个数bufunsafe.Pointer//环形队列指针......
  • NET 元组（Tuple）数据结构
    .NET中的元组（Tuple）是一种数据结构，用于将多个不同类型的值组合成单个复合值。这使得你可以在没有创建专门的类或结构体的情况下，从方法中返回多个值，或者在多个部分之间传递一组值。.NET提供了两种主要的元组类型：System.Tuple类这是.NETFramework4.0中引入的早期元组类型。......
  • 网安习题中英文
    第一章《计算机安全手册》将术语“计算机安全”定义为TheNISTComputerSecurityHandbookdefinesthetermcomputersecurityas为实现维护信息系统资源（包括硬件、软件、固件、信息/数据和电信）的完整性、可用性和机密性的适用目标而对自动化信息系统提供的保护Theprotect......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99