-7

抱歉，我没有时间在这里写一篇长篇大论。这是我目前正在做的练习考试中的一个问题，我所有的大学资源都处于离线状态（我知道很棒的大学）。我完全不知道如何开始这个。有人可以带我过去吗？我不是最擅长数学的人。

考虑以下递归方法：

public static int triple(int x) {
    if (x == 0) return 0;
    else return add(3, triple(decrement(x)));
}

假设递减方法的最坏情况时间性能是常数，并且加法方法的第二个参数是线性的（即 add(x,y) 的时间可以表示by+a为某些常数b和a），推导出最小big O的用 x 来描述三元法的最坏情况时间性能。要导出此方法的复杂性，请确定并扩展前几个方法实例（问题大小）的递归关系，然后推广您的表达式以形成nth case. 展示你的作品。

4

4 回答 4

2

对于特定的 x，triple将使用 0、1、2、... x 递归调用。让我们在递归调用中调用这些参数i。当参数是i时，add的第二个参数是3(i-1)。这意味着这种add调用的成本是线性的i。因此，每个递归调用在 的参数中都是线性的triple。有x这样的调用，所以你得到了算术级数的总和 (0 + 3 + 6 + ...)——这就是 O(n 2 ) 时间复杂度。

您可以使用以下代码：

public class Test
{
  static int time;
  public static int triple(int x) {
    if (x == 0) return 0;
    else return add(3, triple(decrement(x)));
  }
  private static int add(int i, int j) {
    System.out.println("Spending " + j);
    time += j;
    return i + j;
  }
  private static int decrement(int x) { time++; return x-1; }
  public static void main(String[] args) {
    for (int i = 1; i < 100; i+=10) {
      time = 0;
      System.out.format("triple(%d)=%d; time=%d\n", i, triple(i), time);
    }
  }
}
于 2012-06-21T17:22:33.063 回答
1

形成一个表格，将 x 的值映射到三元组方法执行的次数。然后形成两者之间的关系。

x |  executions |              Executions
-------------------------------------
0  | T(0)                     |  0 A(0)
1  | T(1) + A(3,1) + T(0)     |  3 A(1)
2  | T(2) + + A(3,1) + T(1)   |  6 A(2)
3  | T(3) + A(3,1)            |  9 A(3)

   Time Complexity for T= T(n)+T(n-1)+...+T(n-n)
   Number of add calls is linear O(n)   

   nth term for number of executions
   Un = 3+(n-1)d
      = 3+(n-1)3

   the sum of the an arithmetic series making it O(n^2)
于 2012-06-21T16:55:44.403 回答
1

首先，计算给定 x 递归调用三元组的频率。像上面建议的那样做一张桌子。这将为您提供广义术语的一部分。

其次，对于三元组的每次执行，您可以拥有的最坏情况时间复杂度是多少？提示，这是由 add() 函数确定的。

然后概括。

于 2012-06-21T17:01:06.363 回答
1

好吧，我最终得出它的方式（并感谢所有发布答案的好人让我继续前进）是接受 Jochen 的建议并制定一个快速的复杂性地图，这使一切变得更加简单。

首先，请注意问题规定 add 是 O(n) 时间。

接下来，一个基本的“三重”调用层次结构：

n  |  Time complexity:
------------------------------------------
1  | T(1) + (T(0) = 1   )
2  | T(2) + (T(1) = ... )
3  | T(3) + (T(2) = ... )

显然，一种模式正在出现……

n  | Time complexity
-------------------------------------------
n  | T(n) + T(n - 1)

所以看起来 T(n) 的时间复杂度是n * T三次T调用的时间复杂度。假设调用的增长源来自add且add的时间复杂度为O(n)，则时间复杂度变为n * n或O(n^2)

谢谢大家，如果我使用了错误的术语或其他什么，请告诉我。

编辑：一些添加已关闭，但仍然是相同的 BigO 表示法。

于 2012-06-21T17:25:08.863 回答