算法复杂度解析与实例

• 花匠小妙招
• 2024-12-03 16:01

解析在下面：

判断题第四个答案错了，应该是F

选择题第七个答案也错了，应该是B

 

p1-2：

感觉这是道数学题，肯定是前一个大，你只要把后面那个的2次方提到前面，这两个数都是logN，前一个系数是N方，后一个是2*N，很明显前一个大，所以增长速度快。

p1-3：

后一个的增速是要上天啊。。。

p1-4：

这个我做错了，答案应该是F，算法复杂度应该是O（logN）（系数没用）。

p1-5：

与上一个同理，与系数无关，还是 O（nlogn）的

p1-6：

这个我也不会，应该是有特殊的时候，求指点

p1-7

这个是很显然的，反例很好举。但是这个题其实不严谨，啥叫问题的规模，我个人的理解可能是问题的输入规模，那这样的话其实程序的运行时间不仅取决于问题的输入规模，还取决于算法的好坏。当然我可能理解有误，但是题确实不严谨

x2-1：

x一定，只要y在变。所以就把循环中的表达式解出来，发现y等于根号x-1。即执行力根号x次，所以选b

x2-2：

这个题有难度，应该是b，现在大概是会了。。。反正能做出来

首先就是ifelse语句，选最大的就成

此外眼睛睁大了看，else里面是3*n不是n的三次方，看仔细了就好啦

else的时间复杂度是O（n平方）

if是O（N的四次方）（/100无影响）

x2-3：

设循环次数为x，这就是首项为1，尾项为x的等差数列，所以加在一起就是x方<n,所以x<根号n，所以选B

x2-4：

同理，第一个循环次数为n，第二个需要算一下，设循环次数为t，每次都除以2，所以2的t次方小于i，所以t<logi

选d

x2-7：

这个做错了，B和D的对比其实就是2和log2（N）的对比，显然B更慢

x2-10：

计算机算法必须具备输入、输出和可行性、确定性和有穷性等五个特性。 (2分)

后面的不用看

1-1

算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (1分)

T         F

作者: DS课程组

单位: 浙江大学

1-2

N​2​​logN和NlogN​2​​具有相同的增长速度。 (2分)

T         F

作者: DS课程组

单位: 浙江大学

1-3

2​N​​和N​N​​具有相同的增长速度。 (2分)

T         F

作者: DS课程组

单位: 浙江大学

1-4

100logN是O(N)的。 (1分)

T         F

作者: DS课程组

单位: 浙江大学

1-5

(NlogN)/1000是O(N)的。 (1分)

T         F

作者: DS课程组

单位: 浙江大学

1-6

在任何情况下，时间复杂度为O(n​2​​) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。 (1分)

T         F

作者: 干红华

单位: 浙江大学

1-7

对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。 (1分)

T         F

2-1

下面代码段的时间复杂度是（）。(2分)

x=n; //n>1

y=0;

while( x≥(y+1)*(y+1) )

y++;

O(1)O(n​1/2​​)O(n)O(log​2​​n)

作者: 周治国

单位: 东北师范大学

2-2

下列代码

if ( A > B ) {

for ( i=0; i<N*N/100; i++ )

for ( j=N*N; j>i; j-- )

A += B;

}

else {

for ( i=0; i<N*2; i++ )

for ( j=N*3; j>i; j-- )

A += B;

}

的时间复杂度是：(2分)

O(N​3​​)O(N​4​​)O(N​5​​)O(N​6​​)

作者: 徐镜春

单位: 浙江大学

2-3

下列函数

int func ( int n )

{ int i = 0, sum = 0;

while ( sum < n ) sum += ++i;

return i;

}

的时间复杂度是：(2分)

O(logn)O(n​1/2​​)O(n)O(nlogn)

作者: 考研试卷

单位: 浙江大学

2-4

下列代码

for(i=0; i<n; i++)

for(j=i; j>0; j/=2)

printf(“%dn”, j);

的时间复杂度是： (3分)

O(N×i)O(N)O(N​2​​)O(NlogN)

作者: DS课程组

单位: 浙江大学

2-5

下面代码段的时间复杂度是（）。 (2分)

x=0;

for( i=1; i<n; i++ )

for ( j=1; j<=n-i; j++ )

x++;

O(n)O(n​2​​)O(n​3​​)O(2​n​​)

作者: 周治国

单位: 东北师范大学

2-6

要判断一个整数N（>10）是否素数，我们需要检查3到√​N​​​之间是否存在奇数可以整除N。则这个算法的时间复杂度是：(2分)

O(N/2)O(√​N​​​)O(√​N​​​logN)O(0.5logN)

作者: 徐镜春

单位: 浙江大学

2-7

下列函数中，哪个函数具有最慢的增长速度：(2分)

N​1.5​​NlogN​2​​N​2​​logNN(logN)​2​​

作者: DS课程组

单位: 浙江大学

2-8

给定N×N×N的三维数组A，则在不改变数组的前提下，查找最小元素的时间复杂度是：(2分)

O(N​2​​)O(NlogN)O(N​3​​logN)O(N​3​​)

作者: DS课程组

单位: 浙江大学

2-9

计算机算法指的是（）。 (2分)

计算方法排序方法解决问题的有限运算序列调度方法

作者: 严冰

单位: 浙江大学城市学院

2-10

计算机算法必须具备输入、输出和（）等五个特性。 (2分)

可行性、可移植性和可扩充性可行性、确定性和有穷性确定性、有穷性和稳定性易读性、稳定性和安全性

相关知识

【AI图像生成网站&Golang】雪花算法
算法很美 笔记 2.递归与算法分析
下列程序段中算法的时间复杂度是 int fun( int n)int i=0,s
破解菜鸟算法题：新手必看的高效解题技巧与实战案例
私家庭院绿化设计实例解析二，精致小路
【10月23日】机器学习实战（一）KNN算法：手写识别系统
实例解析常见花卉拍摄技巧
K近邻算法和鸢尾花问题
花卉种苗繁殖技术与温室生产实例
AI工程师基础知识100题

网址: 算法复杂度解析与实例 https://m.huajiangbk.com/newsview847080.html

上一篇: 柴胡的功效与作用,柴胡的副作用

下一篇: windows环境下electr