算法的执行时间T（n）是多少？

-3

您能否向我解释2种算法的执行时间T（n）是多少？假设执行时间T（N）=的＃处决（A：= A + 1）算法的执行时间T（n）是多少？

算法1：

for i ← 1 to n do 
     for j ← 1 to i do 
      for k ← j to i+j do 
        a ← a + 1 
      end for 
     end for 
end for

算法2：

for i ← 1 to m do 
     for j ← 1 to i^2 do 
      for k ← 1 to j do 
        a ← a + 1 
      end for 
     end for 
end for

来源

2010-01-09 user247133

作业？....... – 2010-01-09 17:10:10

家庭作业？如果是这样，标记它。 – lmsasu 2010-01-09 17:10:13

执行时间T（n）的可以通过计算发生的原子操作的数量来找到（例如，将值a+1指定为a）。在这种情况下，计算数字操作并不那么困难，因为在每个算法中，只有一个操作，其执行次数由循环的固定范围控制。因为这是家庭作业（或者听起来像是这样），我不打算执行计算，但是你是否足够了解嵌套循环以确定每个执行体的执行次数？

来源

2010-01-09 17:12:53 danben

对于这些算法，您应该尝试以n（或m，在算法2中）的形式得出一个表达式。对于这些算法，该表达式将是一个多项式。该多项式的阶数实际上是该算法的O（n）复杂度。现在有了这个提示，你应该能够完成作业。

来源

2010-01-09 17:15:58 Tarydon

他不是在计算复杂度O（n），而是计算执行时间T（n）。 – danben 2010-01-09 17:18:29

@danben：我的错。 – Tarydon 2010-01-09 17:20:56

这里是你如何处理这些：

对于第一，弄清楚有多少次最内层循环执行作为i和j功能。致电此号码f(i, j)。然后我们注意到

sum(i = 1 to n) sum(j = 1 to i) f(i, j)

将是所需的答案。那么这是计算这个总和的问题。我会给你一个提示：答案涉及知道如何总结连续的正方形和连续的整数。（我100％确定你的教授在课堂上对此有所了解。）

对于第二种，类似的方法。对于这一个，你需要知道连续四次幂的总和，再次是连续的平方和。

我有这两个答案;如果你想，发布一个解决方案，我会检查我的并提供意见。

来源

2010-01-09 17:27:52 jason

算法的执行时间T（n）是多少？

回答

相关问题