java - 在算法的复杂性中取什么作为n

Question

我之前在这个话题上做过什么:

这个话题我纠结了好久。我在“Java 算法”和 Adam Drozdek 的书中阅读了几个计算简单算法复杂度的示例，并搜索了论坛，但我找不到这个问题。

问题:

在《Algorithms in 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 并且它已经从该 View 计算了复杂性，因此结果是 n。

Answer 1

我觉得你有点倒退了:

In some books such as "Algorithms in Java", for calculating time complexity of an algorithm, a certain statement is taken as n. But in another book of "Adam Drozdek", the number of times a loop is run is taken as n.

我不认为这是正确的。

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

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

---

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

(实际上，您在推理时犯了一个错误。循环的迭代次数与 r 不成正比。即使在最坏的情况下也不成正比。再考虑一下!! )