数据结构算法的时间复杂度

答案:4 悬赏:80 手机版

解决时间 2021-12-26 07:29

提问者网友：蓝莓格格巫
2021-12-25 14:02

x=n;
while(x>=(y+1)*(y+1))
y=y+1
求时间复杂度要有详细的算法思想

最佳答案

五星知识达人网友：duile
2021-12-25 15:29

按照分析惯例，假设所有单一运算的时间复杂度均为1

x=n; ......1
while(x>=(y+1)*(y+1)) ......4(两次加法、1次乘法、1次比较)
y=y+1 ......1

时间复杂度 = 1 + (4 + 1) x 循环次数

循环次数是由n和y的初始值决定的，假设循环次数为N，y的初始值为y0，y的结束状态为yn，有
x < (yn + 1)*(yn + 1) ......假设y的初始值为整数，则yn为满足该式的最小整数
N = (yn - y0) / 1 ......因为每次循环y的递增量为1
1式简化为 x = (yn + 1)*(yn + 1)，可得：yn = n^(1/2) - 1
所以N = n^(1/2) - 1 - y0
采用大O表示法，仅考虑最高次项，则求N的复杂度为O(n^(1/2))

进而求得你这3行代码的
总体复杂度 = 1 + (4 + 1) x O(n^(1/2))

由于已知的常数项及非最高次项通常会被忽略（大O精神），所以总时间复杂度为O(n^(1/2))

全部回答

1楼网友：一叶十三刺
2021-12-25 18:37

1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为t(n)。 2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度t(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用t(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，t（n)/f(n)的极限值为不等于零的常数，则称f(n)是t(n)的同数量级函数。记作t(n)=o(f(n)),称o(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为o(1),另外，在时间频度不相同时，时间复杂度有可能相同，如t(n)=n^2+3n+4与t(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为o(n^2)。按数量级递增排列，常见的时间复杂度有：常数阶o(1),对数阶o(log(2)n),线性阶o(n), 线性对数阶o(nlog(2)n),平方阶o(n^2)，立方阶o(n^3),...， k次方阶o(n^k),指数阶o(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

2楼网友：胯下狙击手
2021-12-25 18:03

n^(1/2)-y0=O(N^(1/2))

3楼网友：琴狂剑也妄
2021-12-25 16:34

************我谈********************** “如果执行时间的算法不按照问题规模n的增加而增长，即使成千上万的语句的算法，其执行的时间，但也有大量的常数。该算法的时间复杂度是O（1）。“ 不要明白这一点吗？所以该算法是不是说多少单一的语言温度=; = J; J =温度; />共三种语言中，和每个频率是1，且每个频率可以被认为是O（1），则T（n）的= O的（1）+ O（1）+ O（1）= O（ 1）。以下四个语句： scanf的（“为％d”，＆N）; = N; （I = 0，

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息