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 回答