1

我以前在这个话题上做过什么：

我已经在这个话题上停留了很长时间。我已经阅读了“Java 中的算法”和 Adam Drozdek 的书中计算简单算法复杂度的几个示例，并搜索了论坛，但我找不到这个问题。

问题：

在《Java 中的算法》等一些书籍中，为了计算算法的时间复杂度，将某条语句取为 n。但在《Adam Drozdek》的另一本书中，循环运行的次数被取为 n。因此，如果我用一个 n 来计算复杂度，那么在另一本书中，n 被视为其他东西，因此我计算的复杂度就变得错误了。示例如下。那么，我们如何才能就同一个程序的复杂性达成一致呢？

例子

有一个顺序搜索的例子。这是代码。

static int search(int a[], int v, int l, int r)   { 
    int i;     
    for (i = l; i <= r; i++)       
        if (v == a[i]) return i;     
    return -1;
} `

考虑最坏的情况：

我认为 r 等于 n。所以循环运行n次......

1）比较和增量，比较运行n次，所以是3n。

2) 初始化和声明并返回 -1 运行 1 次，即 3。

所以方程变为

3n+ 3，复杂度为 O(n)。但本书正在考虑否。比较为 n 并且它已经从该视图计算了复杂度，因此结果是 n。

4

4 回答 4

4

我认为你有点倒退：

在《Java 中的算法》等一些书籍中，为了计算算法的时间复杂度，将某条语句取为 n。但在《Adam Drozdek》的另一本书中，循环运行的次数被取为 n。

我不认为这是正确的。

trueN确实是问题的一些缩放变量。例如，如果您正在分析字符串搜索，它可能是字符串的长度，或者如果您正在分析集合操作，它可能是集合中元素的数量。

您发现的那些示例是“某些语句”或“循环”主体的执行次数与缩放变量之间存在关系。请注意，可以有多个缩放变量，并且缩放变量不一定是算法的形式参数之一。（暗示！！）

在您的示例中，您发现r循环执行的次数和值之间存在关系。所以在这种情况下，r将是问题/算法的缩放变量。

（实际上，您的推理错误。循环的迭代次数与 不成正比r。即使在最坏的情况下也不成正比。请多考虑一下！！）

于 2013-09-07T07:53:11.567 回答
3

我认为没有分歧。

该算法具有线性运行时复杂度。对于两倍大小的范围，它需要两倍的时间。

你们都同意复杂性是 O(n)。就迭代次数（书）和机器指令数量（你）而言。您的两种计数方式在衡量运行时间方面应该大致相同（这就是运行时复杂性的含义）。

于 2013-09-07T07:50:36.750 回答
0

正如斯蒂芬已经提到的那样，重要的是扩展以及您的算法如何使用该可扩展实体。

引用你的例子：

static int search(int a[], int v, int l, int r)   { 
    int i;     
    for (i = l; i <= r; i++)       
        if (foo(a)) return something;     
    return -1;
}

如果您的比较使用可扩展实体（即数组）来做出某些决定，那么该特定值将导致复杂性。

同样，如果您在比较函数中进行相同数量的计算而不管任何可扩展实体，那么它都没有贡献。例如，如果函数 foo 总是使用让我们说 5 个机器指令来执行它的工作，那么它基本上是一个常量操作。

在您的情况下，比较每次只是一个操作，因此不会改变 O(n) 复杂度。

于 2013-09-07T08:01:43.667 回答
0

听起来术语“复杂性”（以及术语的重载）可能会引起混淆。

这3n + 3是对程序复杂性的更准确描述。但是，在计算机科学中，我们很少关心3nvsn或“+ 3”与“+ 0”，因为 (a) big-O 复杂度要重要得多，并且 (b) 当 big-O 复杂度相同时，许多其他因素开始发挥作用来区分算法。例如，“+ 3”语句每个都可能是非常昂贵的操作或便宜的，这取决于它们所做的事情。在这些情况下，在比较具有相同 big-O 复杂度的算法时，实际测量被测代码或实时生产的时间会得到更好的结果。

因为在讨论算法的复杂性时我们很少关心这些常数，所以我们经常将术语复杂性与算法的大 O 复杂性互换。

顺便说一下，n是驱动算法迭代次数的输入值。除此之外，它实际上可以是任何东西——它不限于成为程序中的实际变量。例如，一个在从文件中读取输入时循环的程序将具有n= 从文件中读取的输入数。

于 2013-09-07T08:03:31.690 回答