给出下面伪代码的精确和渐近答案

发布于 2024-11-28 03:19:44 字数 507 浏览 7 评论 0原文

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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

朮生 2024-12-05 03:19:44

这听起来像是家庭作业,但是,考虑到一些因素,该伪代码的渐近复杂度应该是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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文