精确的输入大小和时间复杂度

Question

在谈论时间复杂度时，我们通常使用 n 作为输入，这并不是实际输入大小的精确度量。我无法证明，当使用特定大小的输入（s）时，算法仍处于相同的复杂性类别中。

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

如何表明顺序搜索或任何算法保持相同的复杂性类别（在本例中为线性时间）？我知道需要进行某种替换，但我很不稳定关于如何得出结论。

编辑

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

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

Answer 1

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

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

L是表示最大整数的变量。
n 是一个变量，表示输入的大小。
L 不再是 n 的具体值。

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

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

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

复杂度为 n

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

---

编辑：

您的值在编码每个值所需的位数方面将是统一的。如果输入是 32 位整数的列表，则 c = 32，即每个整数的位数。复杂度为 32*n =>在）。

就L而言，如果L是最大值，lg L 是对L进行编码所需的位数，则lg L 是常数c。以位计算的复杂度为 O(n) = c*n，其中 c = lg L 是恒定的特定输入大小。

Answer 2

据我所知，最大数量
顺序搜索完成的步骤是，
显然， 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。

Answer 3

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

这里< /a> 是来源。