-3

问题01： 当我测量一个算法的复杂度时，如何找到T(1)？

例如我有这个算法

Int Max1 (int *X, int N)
{
  int a ;
  if (N==1) return X[0] ;
  a = Max1 (X, N‐1);
  if (a > X[N‐1]) return a;
  else return X[N‐1];
}

我怎样才能找到 T(1)？

问题2 ： 

T(n)= T(n-1) + 1 ==> O(n)

这个等式中的“1”是什么意思

亲切地

4

3 回答 3

1

答案 1. 您正在寻找复杂性。你必须决定你想要什么样的案例复杂度：最好的、最坏的或平均的。根据您选择的内容，您会以不同的方式找到 T(1)：

  • 最佳：想想你的算法可以得到的最简单的长度为 1 的输入。如果您在列表中搜索一个元素，最好的情况是该元素是列表中的第一个元素，并且您可以让 T(1) = 1。
  • 最差：想想你的算法可以得到的最难的长度为 1 的输入。也许你的线性搜索算法对大多数长度为 1 的输入执行 1 条指令，但是对于列表 [77]，你需要 100 步（这个例子有点做作，但算法完全有可能采取更多或更少的步骤，具体取决于与输入的“大小”无关的输入属性）。在这种情况下，您的 T(1) = 100。
  • 平均：考虑您的算法可以获得的所有长度为 1 的输入。为这些输入分配概率。然后，计算所有可能性的平均 T(1) 以获得平均情况 T(1)。

在你的情况下，对于长度为 1 的输入，你总是返回，所以你的 T(n) = O(1) （实际数字取决于你如何计算指令）。

回答 2。在这种情况下，“1”表示指令的精确数量，在某些指令计数系统中。它与 O(1) 的区别在于 O(1) 可以表示不依赖于（根据、趋势等）输入的任何数字（或数字）。您的等式表示“在大小为 n 的输入上评估函数所需的时间等于在大小为 n - 1 的输入上评估函数所需的时间，再加上一条额外的指令”。

于 2013-01-03T17:20:44.880 回答
1

Max1(X,N-1)是实际的算法，其余的是一些检查，O(1) 无论输入如何，所用的时间都是相同的。

Max1我只能假设的函数是在数组中找到数组最高数，这将是O(n)因为它会以线性方式随时间增加到输入 n 的数量。

另外据我所知，在大多数算法中，1 代表 1，只有字母具有可变含义，如果您的意思是它们是如何得到的

T(n-1) + 1到O(n)，这是由于您忽略了系数和低阶项，所以 1 是两种情况都被忽略了O(n)

于 2013-01-03T15:52:21.253 回答
1

T( n ) 是所谓的“ n的函数”，也就是说，n是一个“变量”（意味着您可以用不同的值替换它的位置），并且n的每个特定（有效）值将确定T( n )的对应值。因此，T(1) 仅表示“当n为 1时 T( n ) 的值”。

所以问题是，对于输入值为 1，算法的运行时间是多少？

于 2013-01-03T18:17:43.197 回答