1

在谈论时间复杂度时,我们通常使用n作为输入,这并不是对实际输入大小的精确度量。我无法证明,当对输入(s)使用特定大小时,算法保持在相同的复杂度类中。

例如,采用一个简单的顺序搜索算法。在最坏的情况下,它需要 W(n) 时间。如果我们应用特定的输入大小(以 2 为底),则顺序应该是 W(lg L),其中 L 是最大整数。

我如何证明顺序搜索或任何算法保持相同的复杂性类别,在这种情况下是线性时间? 我知道需要进行某种替代,但我对如何得出结论感到不安。

编辑

我想我可能已经找到了我正在寻找的东西,但我并不完全确定。

如果将最坏情况的时间复杂度定义为 W(s),即输入大小为 s 的算法完成的最大步数,则根据输入大小的定义,s = lg n,其中 n 是输入。那么,n = 2^s,得出时间复杂度为W(2^s),指数复杂度的结论。因此,二进制编码的算法性能是指数的,而不是线性的,因为它在数量级上。

4

3 回答 3

4

在谈论时间复杂度时,我们通常使用 n 作为输入,这并不是对实际输入大小的精确度量。我无法证明,当对输入使用特定大小时,算法保持在相同的复杂度类中。

例如,采用一个简单的顺序搜索算法。在最坏的情况下,它需要 W(n) 时间。如果我们应用特定的输入大小(以 2 为底),则顺序应该是 W(lg L),其中 L 是最大整数。

L是表示最大整数的变量。 n是表示输入大小的变量。 L不再是一个特定的值,而不是n

当您应用特定值时,您不再谈论复杂性类,而是谈论该类的实例。

假设您正在搜索一个包含 500 个整数的列表。换句话说,n = 500

顺序搜索的最坏情况复杂度等级是O(n)

复杂度为n

最坏情况复杂度的具体实例是 500


编辑:

您的值将在编码每个值所需的位数方面保持一致。如果输入是 32 位整数的列表,则 c = 32,即每个整数的位数。复杂度为 32*n => O(n)。

就L而言,如果L是最大值,lg L是编码L所需的比特数,那么lg L就是常数c。您的位复杂度为 O(n) = c*n,其中 c = lg L 是特定的特定输入大小。

于 2011-05-18T15:12:44.100 回答
1

正如 Lucia Moura 所说:“除了一元编码之外,自然数的所有其他编码都具有多项式相关的长度”

是来源。请看第 19 页。

于 2011-05-18T15:50:20.180 回答
1

我所知道的是,顺序搜索完成的最大步数显然是 cn^2 + nlg L。cn^2 是增加循环和进行分支的步数。

这根本不是真的。顺序搜索完成的最大步数将是 c*n,其中 n 是列表中的项目数,c 是某个常数。那是最坏的情况。没有 n^2 分量或对数分量。

例如,一个简单的顺序搜索将是:

for (int i = 0; i < NumItems; ++i)
{
    if (Items[i] == query)
        return i;
}
return -1;

使用该算法,如果您搜索每个项目,则一半的搜索将需要少于NumItems/2迭代的次数,而一半的搜索将需要NumItems/2或更多的迭代。如果您搜索的项目不在列表中,则需要NumItems迭代来确定。最坏情况下的运行时间是NumItems迭代。平均情况是NumItems/2迭代。

实际执行的操作数是某个常数C,乘以迭代次数。平均来说是C*NumItems/2

于 2011-05-18T15:52:27.543 回答