给出下面伪代码的精确和渐近答案
for i <--- 1 step i <--- 2* i while i< n do
for j <--- 1 step j <---2* j while j<n do
if j = 2*i
for k = 0 step k <--- k+ 1 while k < n do
.... CONSTANT NUMBER OF ELEMENTARY OPERATIONS
end for
else
for k<--- 1 step k<-- 3*k while k<n do
...CONSTANT NUBER OF ELEMENTARY OPERATIONS
end for
end if
end for
end for
作为 n 的函数,以下代码片段的运行时间是多少?
“精确答案”是指在确定渐近运行时间之前与代码相关的方程。
for i <--- 1 step i <--- 2* i while i< n do
for j <--- 1 step j <---2* j while j<n do
if j = 2*i
for k = 0 step k <--- k+ 1 while k < n do
.... CONSTANT NUMBER OF ELEMENTARY OPERATIONS
end for
else
for k<--- 1 step k<-- 3*k while k<n do
...CONSTANT NUBER OF ELEMENTARY OPERATIONS
end for
end if
end for
end for
What is the running time for the following code fragment as a function of n?
The 'exact answer' refers to the equation relating to the code BEFORE you determine the asymptotic running time.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
这听起来像是家庭作业,但是,考虑到一些因素,该伪代码的渐近复杂度应该是
O(n*log(n))
。您无法准确估计运行时间,因为它很大程度上取决于您的系统。
It sounds as homework, however, making a few considerations, the asymptotic complexity of that pseudo code should be
O(n*log(n))
.You cannot estimate exactly the running time since it highly depends on your system.