0 
for i <- 1 to n 
  for j <- i to n
    for k <- i to j

第二个循环的运行时间的数学表达式是什么？

是 n = n^2 的 j = 1 到 n 的总和吗？

你如何推导出它，因为它同时依赖于 i 和 n？

4

1 回答 1

1

让我们以两种方式解决这个问题：

1.解决方案

如果您需要计算第二个循环运行时函数，则必须将其表示为 和 的n函数i。因此，您将修复i，因为它作为常数进入第二个循环，并且您不会在第二个或第三个循环的任何地方更改它的值。如果您想了解为什么第二个循环运行时间同时取决于i和，您可以以等效形式编写您的算法n：

for i <- 1 to n 
   doSomething(i,n)


  doSomething(i,n):
    for j <- i to n
     for k <- i  to j
       doStuffHere() //

When j=i,doStuff()只执行一次，因为j=iand k=j=i, 所以循环在 1 次迭代后停止。

当j=i+1,doStuff()被执行 2 次，以此类推。

您可以得出一个规则，即对于 的任何值j，doStuff()执行(j-i+1)次数，即 1 次 when j=i，2 次 when j=i+1，3 次 when j=i+3，...，n-i+1 次 when j=i。这意味着运行时间函数是：

f(n,i) = 1+2+3+...+(n-i+1) = (n-i+1)*(n-i+1+1)/2 =
       = (n-i+1)(n-i+2)/2

稍后，当您尝试推导整个算法的复杂度函数时，您会看到对于从 1 到 n 的每个 i，您都有 f(n,i) doStuff()，因此整个算法将具有运行时间：

RT(n) = f(1,n) + f(2,n) + f(3,n) + .. + f(n,n)

您将不得不在这里做一些数学运算并使用公式计算级数总和。但是，还有另一种方法，更优雅，但可能难以理解。

2.解决方案

很明显，对于算法中的每个 j 和 k：

  • i <= j,k <= n

  • k >= j

    因此，您的代码实际上是从 [i,n] 中选择两个正整数 j 和 k，其中 j<=k。包含这些对 j,k 的集合实际上是重复的组合，我们从 n-i+1 个重复的元素中选择两个元素。不要感到困惑，因为在某些选择中，第一个数字不会小于第二个。你总是可以切换它们，即以非降序重写它们，然后认为第一个是你的j，第二个是你的k。这两个数字可以以 (n-i+1)(n-i+2)/2 种方式选择，这就是您的算法的运行时间函数。通过更多的思考和更少出错的数学计算，您可以以更优雅的方式获得解决方案。如果您尝试确定整个算法的运行时间函数，则同样的逻辑适用。

    与数学公式的有用链接

  • http://en.wikipedia.org/wiki/Combinations

  • http://en.wikipedia.org/wiki/Arithmetic_progression
  • 还有更多链接，但由于我是这里的新用户，所以在获得 10 声望点之前，我不能发布超过两个超链接。:)
于 2013-01-17T14:30:36.060 回答