导言
本篇章题目出自:王道考研系列丛书——《2024年数据结构考研复习指导》课后习题。
题目主要考察的是对时间复杂度的分析,在前面的篇章中我们知道时间复杂度是与问题规模n和输入的值k有关的,但是我们在分析时间复杂度时都是以最坏时间复杂度进行分析,这样能确保算法的运行时间不会比它更长。
分析方法与步骤
对于时间复杂度的分析,我自己的经验是通过递进语句与条件判断语句来找出程序运行时间与问题规模之间的关系。
因为我们在分析时间复杂度是都是分析的最坏时间复杂度,所以此时是忽略输入值带来的影响,默认初始值为最小值,之后我们只需要确认最小值是如何通过递进条件来逼近问题规模就行了。
这里我通过下面两个列子来说明:
单层循环
void Func(int n)
{
for (int i = 0; i < n; i++)
{
printf("hello worldn");
}
}
在这个函数中,我们想要分析它的时间复杂度,可以按照以下步骤一步一步来分析:
第一步:找到问题规模
- 当变量 i 执行 1 次递进语句时,i 就会从0变成1;
- 当变量 i 执行 t 次递进语句时,i 就会从0变成 t;
- 当
t = n
时,i 就会从0变成 n;
因此执行次数与问题规模之间的关系就是t = n
;
第四步:写成反函数
- 在得到执行次数与问题规模之间的关系表达式之后,我们就需要找到表达式的反函数,并将其改写成
=
T
(
n
)
t = T(n)
改写的方式很简单,我们只需要将执行次数 t 的系数变为1就行。
比如这里的t
=
n
t = n
t
=
T
(
n
)
=
n
t = T(n) = n
第五步:改写表达式
- 在得到执行次数 t 关于问题规模 n 的表达式之后,我们只需要在问题规模这一侧在n的前面加一个
O
O
此时我们就能得到T
(
n
)
=
O
(
n
)
T(n) = O(n)
嵌套循环
void Func2(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("one piecen");
}
}
}
在这个函数中我们可以看到,此时函数是由两层循环组成的,我们要分析它就需要由外到内,逐层分析;
-
外层循环
- 问题规模
- 递进方式
- 写成反函数
因为此时t的系数已经为1,所以我们可以很容易得到表达式
t
=
T
(
n
)
=
n
t = T(n) = n
t=T(n)=n;
- 改写表达式
现在我们只需要在 n 前面加一个O就可以得到时间复杂度的表达式了,即
T
(
n
)
=
O
(
n
)
T(n) = O(n)
T(n)=O(n);
-
内层循环
- 问题规模
- 递进方式
- 写成反函数
因为此时t的系数已经为1,所以我们可以很容易得到表达式
t
=
T
(
n
)
=
n
t = T(n) = n
t=T(n)=n;
- 改写表达式
现在我们只需要在 n 前面加一个O就可以得到时间复杂度的表达式了,即
T
(
n
)
=
O
(
n
)
T(n) = O(n)
T(n)=O(n);
嵌套循环的规则是最外层循环执行一次,内层循环要走完整个循环流程。对于这个代码来说,外层循环要执行n次,每执行一次,内层循环就要执行n次,即外层循环执行n次,内层循环就要执行n+n+n+……+n=n*n次;
T
(
n
)
=
O
(
n
)
∗
O
(
n
)
=
n
∗
n
=
n
2
=
O
(
n
2
)
T(n) = O(n) * O(n) = n * n = n^2 = O(n^2)
T(n)=O(n)∗O(n)=n∗n=n2=O(n2);
现在大家应该对时间复杂度的分析有点感觉了,接下来我们就通过下面的习题来巩固一下;
单项选择题
题目1
1.以下算法的时间复杂度为()
`void fun(int n)
{
int i = 1;
while (i <= n)
{
i = i * 2;
}
}`
A
.
O
(
n
)
A.O(n)
A.O(n)
B
.
O
(
n
2
)
B.O(n^2)
B.O(n2)
C
.
O
(
n
l
2
n
)
C.O(nlog2n)
D
.
O
(
l
o
2
n
)
D.O(log2n)
题目解析
这一题是一个单层循环的题目,下面我们按步骤来对这个循环进行分析;
第一步:问题规模
- 通过条件语句可知,这里的问题规模为n;
第二步:递进方式
- 通过对象语句和递进语句可知,此时的递进方式是从1开始,每次扩大2倍,当执行t次时,就要扩大
2
∗
2
∗
2
∗
…
…
∗
2
=
2
t
2*2*2*……*2=2^t
2∗2∗2∗……∗2=2t倍;
- 当执行t次后,变量i与n相等时,可以得到
2
t
=
n
2^t = n
2t=n;
第四步:写成反函数
第五步:改写表达式
所以这一题的答案为:
题目2
2.以下算法的时间复杂度为()
void fun(int n)
{
int i = 0;
while (i * i * i <= n)
{
i++;
}
}
A
.
O
(
n
)
A.O(n)
A.O(n)
B
.
O
(
n
l
o
g
n
)
B.O(nlogn)
B.O(nlogn)
C
.
O
(
n
1
/
3
)
C.O(n^{1/3})
C.O(n1/3)
D
.
O
(
n
1
/
2
)
D.O(n^{1/2})
D.O(n1/2)
题目解析
这一题也是一个单层循环的题目,下面我们按步骤来对这个循环进行分析;
第一步:问题规模
- 这里的条件语句为
i
∗
i
∗
i
<
=
n
i*i*i<=n
i∗i∗i<=n,此时我们可以得到
i
3
<
=
n
i^3<=n
i3<=n ,即
i
<
=
n
1
/
3
i<=n^{1/3}
i<=n1/3;所以这里的问题规模为
n
1
/
3
n^{1/3}
n1/3;
第二步:递进方式
- 通过对象语句和递进语句可知,此时的递进方式是从0开始,每次增加1,当执行t次时,从0变成了t;
- 当执行t次后,变量i与
n
1
/
3
n^{1/3}
n1/3相等时,可以得到
t
=
n
1
/
3
t = n^{1/3}
t=n1/3;
第四步:写成反函数
- 此时t的系数已经是1了,所以我们可以得到
t
=
T
(
n
)
=
n
1
/
3
t = T(n) = n^{1/3}
t=T(n)=n1/3;
第五步:改写表达式
- 此时我们在
n
1
/
3
n^{1/3}
n1/3的前面加一个O就能得到
T
(
n
)
=
O
(
n
1
/
3
)
T(n) = O(n^{1/3})
T(n)=O(n1/3);
所以这一题的答案为:
C
.
O
(
n
1
/
3
)
C.O(n^{1/3})
C.O(n1/3);
题目3
3.在下列程序段中,
n
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
)
A.O(n)
A.O(n)
B
.
O
(
n
l
o
g
n
)
B.O(nlogn)
B.O(nlogn)
C
.
O
(
n
3
)
C.O(n^3)
C.O(n3)
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2)
题目解析
这一题是一个嵌套循环的题目,下面我们按步骤来对这个循环进行分析;
- 外层循环
- 问题规模
- 递进方式
- 执行次数与问题规模的关系
- 写成反函数
- 根据他们的关系式,我们可以得到表达式
t
=
T
(
n
)
=
n
t = T(n) = n
t=T(n)=n ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
n
)
T(n) = O(n)
T(n)=O(n);
- 内层循环
- 问题规模
- 递进方式
- 执行次数与问题规模的关系
- 写成反函数
- 根据他们的关系式,我们可以得到表达式
t
=
T
(
n
)
=
n
−
2
t = T(n) = n-2
t=T(n)=n−2 ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
n
−
2
)
T(n) = O(n-2)
T(n)=O(n−2);
- 合并表达式
现在我们需要分析一下这里合并表达式的方式,具体是通过加法规则进行合并还是通过乘法规则进行合并;
- 嵌套循环的规则是最外层循环执行一次,内层循环要走完整个循环流程。
- 对于这个代码来说,外层循环总共要执行
n
−
1
n-1
n−1次,每执行一次,内层循环就要执行 i 次;
- 因为 i 的值会随着执行次数的增加而减少,所以内层循环的执行次数会依次减少,所以内层循环的总次数应该是:
(
n
−
1
)
+
(
n
−
2
)
+
(
n
−
3
)
+
…
…
+
3
+
2
(n-1)+(n-2)+(n-3)+……+3+2
(n−1)+(n−2)+(n−3)+……+3+2
- 根据求和公式:
(
首项
+
尾项
)
×
项数
/
2
(首项+尾项)×项数/2
(首项+尾项)×项数/2
我们能够得到最终的表达式T
(
n
)
=
(
n
2
−
n
−
2
)
/
2
T(n) = (n^2-n-2)/2
T(n)=(n2−n−2)/2;
- 这里我们将表达式的每一项的系数都改为1,并在每一项的前面加上O,就能得到
T
(
n
)
=
O
(
n
2
)
+
O
(
n
)
+
O
(
1
)
T(n) = O(n^2)+O(n)+O(1)
T(n)=O(n2)+O(n)+O(1);
所以此时我们需要使用加法规则来进行合并,即T
(
n
)
=
O
(
n
2
)
+
O
(
n
)
+
O
(
1
)
=
(
O
(
n
2
)
,
O
(
n
)
,
O
(
1
)
)
=
O
(
n
2
)
T(n) = O(n^2)+O(n)+O(1) = max(O(n^2),O(n),O(1)) = O(n^2)
T(n)=O(n2)+O(n)+O(1)=max(O(n2),O(n),O(1))=O(n2);
所以这一题的答案为:
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2);
题目4
for (i = 1; i <= n; i++)
{
for (j = 1; j <= 2 * i; j++)
{
m++;
}
}`
A
.
n
(
n
+
1
)
A.n(n+1)
A.n(n+1)
B
.
n
B.n
B.n
C
.
n
+
1
C.n+1
C.n+1
D
.
n
2
D.n^2
D.n2
题目解析
这一题也是一个嵌套循环的题目,这一题与上一题相比,区别不大,我们根据上一题的解题步骤一步一步来分析即可;
- 外层循环
- 问题规模
- 我们根据条件语句
i <= n;
可以得到,外层循环的问题规模为n;
- 递进方式
- 执行次数与问题规模的关系
- 写成反函数
- 根据他们的关系式,我们可以得到表达式
t
=
T
(
n
)
=
n
t = T(n) = n
t=T(n)=n ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
n
)
T(n) = O(n)
T(n)=O(n);
- 内层循环
- 问题规模
- 递进方式
- 执行次数与问题规模的关系
- 当
t
=
2
n
−
1
t = 2n – 1
t=2n−1 时,我们就能得到
1
+
t
=
1
+
2
n
−
1
=
2
n
1+t =1+2n – 1 = 2n
1+t=1+2n−1=2n ;
也就是说,此时的执行次数与问题规模的关系为t
=
2
n
−
1
t = 2n – 1
t=2n−1 ;
此时因为问题规模是在逐渐增加的,所以我们需要保留这个表达式,不能像前面一样省略这个1;
- 写成反函数
- 根据他们的关系式,我们可以得到表达式
t
=
T
(
n
)
=
2
n
−
1
t = T(n) = 2n-1
t=T(n)=2n−1 ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
2
n
−
1
)
T(n) = O(2n-1)
T(n)=O(2n−1);
- 合并表达式
现在我们需要分析一下这里合并表达式的方式,具体是通过加法规则进行合并还是通过乘法规则进行合并;
- 嵌套循环的规则是最外层循环执行一次,内层循环要走完整个循环流程。
- 对于这个代码来说,外层循环要执行n次,每执行一次,内层循环就要执行n次;
- 这里外层循环总共要执行
n
n
n次,但是内层循环的执行次数会依次增加,所以内层循环的总次数应该是:
2
+
4
+
6
+
…
…
+
2
(
n
−
1
)
+
2
n
2+4+6+……+2(n-1)+2n
2+4+6+……+2(n−1)+2n
- 根据项数公式:
(
尾项
−
首项
)
/
项差
+
1
(尾项-首项)/项差+1
(尾项−首项)/项差+1
以及求和公式:(
首项
+
尾项
)
×
项数
/
2
(首项+尾项)×项数/2
(首项+尾项)×项数/2
我们能够得到最终的表达式T
(
n
)
=
n
2
+
n
T(n) = n^2+n
T(n)=n2+n;
- 这里我们将表达式的每一项的系数都改为1,并在每一项的前面加上O,就能得到
T
(
n
)
=
O
(
n
2
)
+
O
(
n
)
T(n) = O(n^2)+O(n)
T(n)=O(n2)+O(n);
所以此时我们需要使用加法规则来进行合并,即T
(
n
)
=
O
(
n
2
)
+
O
(
n
)
=
(
O
(
n
2
)
,
O
(
n
)
)
=
O
(
n
2
)
T(n) = O(n^2)+O(n) = max(O(n^2),O(n)) = O(n^2)
T(n)=O(n2)+O(n)=max(O(n2),O(n))=O(n2);
所以这一题的答案为:
A
.
n
(
n
+
1
)
A.n(n+1)
A.n(n+1);
题目5
5.设
n
n
x = 2;
while (x < n / 2)
{
x = 2 * x;
}
A
.
O
(
l
o
g
2
n
)
A.O(log2n)
B
.
O
(
n
)
B.O(n)
B.O(n)
C
.
O
(
n
l
o
g
2
n
)
C.O(nlog2n)
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2)
题目解析
这一题是一个单层循环的题目,下面我们按步骤来对这个循环进行分析;
第一步:问题规模
- 通过条件语句可知,这里的问题规模为
n
/
2
n/2
n/2;
第二步:递进方式
- 通过对象语句和递进语句可知,此时的递进方式是从2开始,每次扩大2倍,当执行t次时,就要扩大
2
∗
2
∗
2
∗
…
…
∗
2
=
2
t
2*2*2*……*2=2^t
2∗2∗2∗……∗2=2t倍;
第三步:问题规模与执行次数的关系
- 当执行t次后,变量x与
n
/
2
n/2
n/2相等时,可以得到
2
t
=
n
/
2
2^t = n/2
2t=n/2,这里我们先将两边同时乘以2,得到
2
t
+
1
=
n
2^{t+1} = n
2t+1=n;
第四步:写成反函数
第五步:改写表达式
- 此时我们在
l
o
g
2
n
−
1
log_2n-1
log2n−1的每一项前面加一个O就能得到
T
(
n
)
=
O
(
l
o
g
2
n
)
+
O
(
1
)
T(n) = O(log_2n)+O(1)
T(n)=O(log2n)+O(1);
- 根据加法规则我们可以得到
T
(
n
)
=
O
(
l
o
g
2
n
)
+
O
(
1
)
=
x
(
O
(
l
o
g
2
n
)
,
O
(
1
)
)
=
O
(
l
o
g
2
n
)
T(n) = O(log_2n)+O(1)=max(O(log_2n),O(1))=O(log_2n)
T(n)=O(log2n)+O(1)=max(O(log2n),O(1))=O(log2n);
所以这一题的答案为:
A
.
O
(
l
o
g
2
n
)
A.O(log_2n)
A.O(log2n);
题目6
6.求整数
n
(
n
>
=
0
)
n(n>=0)
int fact(int n)
{
if (n <= 1)
{
return 1;
}
return n * fact(n - 1);
}
A
.
O
(
l
o
g
2
n
)
A.O(log_2n)
A.O(log2n)
B
.
O
(
n
)
B.O(n)
B.O(n)
C
.
O
(
n
l
o
g
2
n
)
C.O(nlog_2n)
C.O(nlog2n)
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2)
题目解析
这一题是一个递归的题目,递归与循环的区别在于对内存的消耗,这个不是我们的重点,我就不展开叙述了,递归与循环的相似之处在于它也是重复的完成一个任务,下面我们就来分析一下它的时间复杂度;
第一步:问题规模
- 通过条件语句可知,这里的递归是从n到1,也就是说递归的问题规模就是n;
第二步:递进方式
第三步:问题规模与执行次数的关系
第四步:写成反函数
n
=
t
+
1
n = t+1
n=t+1这个表达式我们只需要简单的进行移项就能得到
t
=
T
(
n
)
=
n
−
1
t = T(n) = n-1
t=T(n)=n−1;
第五步:改写表达式
所以这一题的答案为:
B
.
O
(
n
)
B.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
(
l
o
g
2
n
)
A.O(log_2n)
A.O(log2n)
B
.
O
(
n
)
B.O(n)
B.O(n)
C
.
O
(
n
l
o
g
2
n
)
C.O(nlog_2n)
C.O(nlog2n)
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2)
题目解析
这一题也是一个嵌套循环的题目,这里的嵌套循环与我们前面做的相比,要稍微简单一点,它更加贴近我们在讲解思路时用的嵌套循环的例子;
- 外层循环
- 问题规模
- 我们根据条件语句
k <= n;
可以得到,外层循环的问题规模为n;
- 递进方式
- 从对象语句
k = 1;
和递进语句k *= 2;
我们可以得到此时每执行一次,起始值就会变为原来的2倍,执行t次,起始值就会变为原来的2
t
2^t
2t倍;
- 执行次数与问题规模的关系
- 当执行t次后时,变量k与问题规模n的值相等,那我们就能得到
2
t
=
n
2^t = n
2t=n ;
也就是说,此时的执行次数与问题规模的关系为2
t
=
n
2^t = n
2t=n ;
- 写成反函数
- 根据他们的关系式,我们在等式两边同时取对数,就可以得到表达式
t
=
T
(
n
)
=
l
o
g
2
n
t = T(n) = log_2n
t=T(n)=log2n ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
l
o
g
2
n
)
T(n) = O(log_2n)
T(n)=O(log2n);
- 内层循环
- 问题规模
- 根据这里的条件语句
j <= n;
我们可以得到,这里的问题规模与外层循环一样,也是n;;
- 递进方式
- 从对象语句
j = 1;
和递进语句j++;
我们可以得到,此时每执行一次,起始值就会加1,执行t次,起始值就会加t;
- 执行次数与问题规模的关系
- 写成反函数
- 根据他们的关系式,我们可以得到表达式
t
=
T
(
n
)
=
n
t = T(n) = n
t=T(n)=n ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
n
)
T(n) = O(n)
T(n)=O(n);
- 合并表达式
现在我们需要分析一下这里合并表达式的方式,具体是通过加法规则进行合并还是通过乘法规则进行合并;
- 嵌套循环的规则是最外层循环执行一次,内层循环要走完整个循环流程。
- 对于这个代码来说,外层循环要执行n次,每执行一次,内层循环就要执行n次;
- 这里外层循环总共要执行
l
o
g
2
n
log_2n
log2n次,所以内层循环的总次数应该是:
n
+
n
+
n
+
…
…
+
n
=
n
∗
l
o
g
2
n
n+n+n+……+n=n*log_2n
n+n+n+……+n=n∗log2n
我们能够得到最终的表达式T
(
n
)
=
n
∗
l
o
g
2
n
T(n) = n*log_2n
T(n)=n∗log2n;
- 这里我们将
n
∗
l
o
g
2
n
n*log_2n
n∗log2n的前面加上O,就能得到
T
(
n
)
=
O
(
n
∗
l
o
g
2
n
)
T(n) = O(n*log_2n)
T(n)=O(n∗log2n);
所以这一题的答案为:
C
.
O
(
n
l
o
g
2
n
)
C.O(nlog_2n)
C.O(nlog2n);
题目8
8.下列函数的时间复杂度为()
int func(int n)
{
int i = 0, sum = 0;
while (sum < n)
{
sum += ++i;
}
return i;
}
A
.
O
(
l
o
g
n
)
A.O(logn)
A.O(logn)
B
.
O
(
n
1
/
2
)
B.O(n^{1/2})
B.O(n1/2)
C
.
O
(
n
)
C.O(n)
C.O(n)
D
.
O
(
n
l
o
g
n
)
D.O(nlogn)
D.O(nlogn)
题目解析
这一题是一个单层循环的题目,现在大家对单层循环的题应该都是有感觉了,下面我们直接来进行分析;
第一步:问题规模
- 通过条件语句可知,这里的问题规模为n;
第二步:递进方式
第三步:问题规模与执行次数的关系
第四步:写成反函数
(
t
2
+
t
)
/
2
=
n
(t^2+t)/2=n
(t2+t)/2=n这个表达式我们先将表达式改写成
t
2
+
2
∗
(
1
/
2
)
∗
t
=
2
n
t^2+2*(1/2)*t=2n
t2+2∗(1/2)∗t=2n,此时我们就可以很容易得到
(
t
+
1
/
2
)
2
=
2
n
+
1
/
4
(t+1/2)^2=2n+1/4
(t+1/2)2=2n+1/4;
之后我们在进行开方移项,即可得到t
=
T
(
n
)
=
(
2
n
+
1
/
4
)
1
/
2
−
1
/
2
t = T(n) = (2n+1/4)^{1/2}-1/2
t=T(n)=(2n+1/4)1/2−1/2;
第五步:改写表达式
- 此时我们将
(
2
n
+
1
/
4
)
1
/
2
−
1
/
2
(2n+1/4)^{1/2}-1/2
(2n+1/4)1/2−1/2 每一项的系数改为1,并在前面加一个O就能得到
T
(
n
)
=
O
(
(
2
n
+
1
/
4
)
1
/
2
)
+
O
(
1
)
T(n) = O((2n+1/4)^{1/2})+O(1)
T(n)=O((2n+1/4)1/2)+O(1);
根据加法规则,我们可很容易的得到T
(
n
)
=
O
(
(
2
n
+
1
/
4
)
1
/
2
)
T(n) = O((2n+1/4)^{1/2})
T(n)=O((2n+1/4)1/2);
此时当n足够大时,这里的1/4是可以忽略不计的,所以我们可以得到表达式:T
(
n
)
=
O
(
(
2
n
)
1
/
2
)
T(n) = O((2n)^{1/2})
T(n)=O((2n)1/2);
此时再将n的系数改为1,就能得到我们最终的时间复杂度的渐近表达式:T
(
n
)
=
O
(
n
1
/
2
)
T(n) = O(n^{1/2})
T(n)=O(n1/2);
所以这一题的答案为:
B
.
O
(
n
1
/
2
)
B.O(n^{1/2})
B.O(n1/2);
题目9
9.设
n
n
x = 0;
while (n >= (x + 1) * (x + 1))
{
x = x + 1;
}
A
.
O
(
l
o
g
n
)
A.O(logn)
A.O(logn)
B
.
O
(
n
1
/
2
)
B.O(n^{1/2})
B.O(n1/2)
C
.
O
(
n
)
C.O(n)
C.O(n)
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2)
题目解析
这一题又是一个单层循环的题目,下面我们直接来分析;
第一步:问题规模
- 这里的条件语句
n >= (x + 1) * (x + 1)
我们需要先将其改写一下,得到表达式x
<
=
n
1
/
2
−
1
x<=n^{1/2}-1
x<=n1/2−1;
现在我们就能得到问题规模为:n
1
/
2
−
1
n^{1/2}-1
n1/2−1;
第二步:递进方式
- 通过对象语句和递进语句可知,此时的递进方式是从0开始,每次增加1,当执行t次时,就要增加t;
第三步:问题规模与执行次数的关系
- 当执行t次后,变量x与
n
1
/
2
−
1
n^{1/2}-1
n1/2−1相等时,可以得到
t
=
n
1
/
2
−
1
t = n^{1/2}-1
t=n1/2−1;
第四步:写成反函数
t
=
n
1
/
2
−
1
t = n^{1/2}-1
t=n1/2−1这个表达式已经是t与n的关系表达式了,所以我们将其改写一下即可得到
t
=
T
(
n
)
=
n
1
/
2
−
1
t = T(n) = n^{1/2}-1
t=T(n)=n1/2−1;
当然这里的1也是可以省略的,即使这里不省略,在后面改写表达式时根据加法规则也会将其省略掉;
第五步:改写表达式
- 此时我们将
n
1
/
2
−
1
n^{1/2}-1
n1/2−1的每一项的系数改为1,并在前面加一个O就能得到
T
(
n
)
=
O
(
n
1
/
2
)
+
O
(
1
)
T(n) = O(n^{1/2})+O(1)
T(n)=O(n1/2)+O(1);
根据加法规则我们就能得到T
(
n
)
=
O
(
n
1
/
2
)
T(n) = O(n^{1/2})
T(n)=O(n1/2);
所以这一题的答案为:
B
.
O
(
n
1
/
2
)
B.O(n^{1/2})
B.O(n1/2);
题目10
10.以下程序段的时间复杂度为()
int sum = 0;
for (int i = 1; i < n; i *= 2)
{
for (int j = 0; j < i; j++)
{
sum++;
}
}
A
.
O
(
l
o
g
n
)
A.O(logn)
A.O(logn)
B
.
O
(
n
)
B.O(n)
B.O(n)
C
.
O
(
n
l
o
g
n
)
C.O(nlogn)
C.O(nlogn)
D
.
O
(
n
2
)
D.O(n^2)
D.O(n2)
题目解析
这一题是一个嵌套循环的题目,看到题目,是不是感觉和上面做的第三题和第四题有点像啊,下面我们来直接进行分析;
- 外层循环
- 问题规模
- 根据条件语句我们可以很容易的得到外层循环的问题规模为n
- 递进方式
- 从对象语句
int i = 1;
和递进语句i *= 2;
我们可以得到,此时每执行一次,起始值就扩大为原来的2倍,执行t次,起始值就会扩大为2
t
2^t
2t;
- 执行次数与问题规模的关系
- 当执行t次时,变量 i 与问题规模 n 相等,我们就能得到
2
t
=
n
2^t = n
2t=n ;
- 写成反函数
- 根据他们的关系式,将等式两边同时取对数,我们可以得到表达式
t
=
T
(
n
)
=
l
o
g
2
n
t = T(n) = log_2n
t=T(n)=log2n ;
- 改写表达式
- 在得到表达式之后,我们在右侧加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
l
o
g
2
n
)
T(n) = O(log_2n)
T(n)=O(log2n);
- 内层循环
- 问题规模
- 递进方式
- 从对象语句
j = 0;
和递进语句j++;
我们可以得到,此时每执行一次,起始值就会加1,执行t次,起始值就会加t;
- 执行次数与问题规模的关系
- 当执行t次时,变量 j 与问题规模 2n 相等,我们就能得到
t
=
2
n
t = 2n
t=2n ;
- 写成反函数
- 根据他们的关系式,我们可以得到表达式
t
=
T
(
n
)
=
2
n
t = T(n) = 2n
t=T(n)=2n ;
- 改写表达式
- 在得到表达式之后,我们将n的系数改为1,并加上O就能得到时间复杂度的渐近表达式
T
(
n
)
=
O
(
n
)
T(n) = O(n)
T(n)=O(n);
- 合并表达式
现在我们需要分析一下这里合并表达式的方式,具体是通过加法规则进行合并还是通过乘法规则进行合并;
- 对于这个代码来说,外层循环要执行
l
o
g
2
n
log_2n
log2n次,每执行一次,内层循环就要执行 i 次;
- 因为 i 的值会随着循环次数的增加而增加,所以内层循环的执行次数会也会随着 i 值的增加而增加,所以内层循环的总次数应该是:
1
+
2
+
4
+
8
+
…
…
+
2
n
1+2+4+8+……+2n
1+2+4+8+……+2n
根据等比数列求和公式:首项
×
(
公
比
n
−
1
)
/
(
公比
−
1
)
=
1
×
(
q
n
−
1
)
/
(
q
−
1
)
首项×(公比^n-1)/(公比-1)=a_1×(q^n-1)/(q-1)
首项×(公比n−1)/(公比−1)=a1×(qn−1)/(q−1)
我们能够得到最终的表达式t
=
1
∗
(
2
l
o
g
2
n
−
1
)
/
(
2
−
1
)
=
n
−
1
t=1*(2^{log_2n}-1)/(2-1)=n-1
t=1∗(2log2n−1)/(2−1)=n−1
所以这一题的答案为:
B
.
O
(
n
)
B.O(n)
B.O(n);
结语
第一章的内容现在我们就全部介绍完了,不知道大家在看完这篇内容后,对时间复杂度的求解还有没有什么问题,这里有个投票大家可以参与一下,我会根据投票情况来决定需不需要再出一篇这个内容,希望大家能够踊跃参与。
接下来,我们将开始进入第二章的内容——线性表。从这个篇章开始,咱们需要有指针和结构体等C语言的基本功,这样才能更好的理解这些内容。为了帮助大家更好的理解,我也会在【C语言必学知识点】专栏中介绍这些知识点,大家记得关注哦!
【数据结构】第一章——绪论
【数据结构】第一章——绪论(1):【数据结构的基本概念】
【数据结构】第一章——绪论(3):【时间复杂度】
【数据结构】第一章——绪论(4):【空间复杂度】
原文地址:https://blog.csdn.net/2301_79458548/article/details/134716258
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_46690.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!