问题约束会改变算法的时间复杂度吗？

Question

假设该算法涉及逐个字符地迭代字符串。

如果我确定字符串的长度小于 15 个字符，那么时间复杂度是 O(1) 还是仍为 O(n)？

Answer 1

这个问题有两个方面——问题的核心是，问题约束能否改变算法的渐近复杂度？答案是肯定的。但随后您给出了一个约束示例（字符串限制为 15 个字符），其中答案是：问题没有意义。这里的许多其他答案都是误导性的，因为它们只涉及第二个方面，但试图就第一个方面得出结论。

\n

形式上，算法的渐近复杂度是通过考虑一组输入来测量的，其中输入大小（即我们所说的n）是无界的。n必须是无界的原因是因为渐近复杂度的定义是这样的陈述“有一些 n ₀使得对于所有 n \xe2\x89\xa5 n ₀ , ...”，所以如果集合不包含大小为n \xe2\x89\xa5 n ₀的任何输入，则此语句是空的。

\n

由于算法可以根据我们考虑的每种大小的输入而具有不同的运行时间，因此我们经常区分“平均”、“最坏情况”和“最佳情况”时间复杂度。以插入排序为例：

\n

\n
• 在一般情况下，插入排序必须将当前元素与数组已排序部分中的一半元素进行比较，因此该算法会进行大约n ² /4 次比较。
\n
• 在最坏的情况下，当数组按降序排列时，插入排序必须将当前元素与已排序部分中的每个元素进行比较（因为它小于所有元素），因此该算法大约执行n ² /2比较。
\n
• 在最好的情况下，当数组按升序排列时，插入排序只需将当前元素与已排序部分中的最大元素进行比较，因此该算法大约进行n次比较。
\n

\n

但是，现在假设我们添加一个约束，即输入数组除最小元素外始终按升序排列：

\n

\n
• 现在平均情况大约进行 3 n /2 次比较，
\n
• 最坏的情况大约进行 2 n次比较，
\n
• 最好的情况是进行n次比较。
\n

\n

请注意，它是相同的算法，即插入排序，但因为我们正在考虑一组不同的输入，其中算法具有不同的性能特征，所以我们最终会得到平均情况下不同的时间复杂度，因为我们对不同的集合取平均值，同样，我们在最坏的情况下得到不同的时间复杂度，因为我们从不同的集合中选择最差的输入。因此，是的，即使算法本身没有改变，添加问题约束也会改变时间复杂度。

\n

但是，现在让我们考虑一个迭代字符串中每个字符的算法示例，并附加了字符串长度最多为 15 个字符的约束。在这里，谈论渐近复杂度是没有意义的，因为集合中的输入大小n不是无界的。这组特定的输入对于进行此类分析无效。

\n

Answer 2

从数学意义上来说，是的。Big-O 表示法描述了算法在极限情况下的行为，如果输入大小有固定的上限，则意味着它具有最大恒定复杂度。

也就是说，背景很重要。所有计算机对其可接受的输入量都有一个实际限制（技术上限）。仅仅因为世界上没有任何东西可以存储一亿字节的数据并不意味着说每个算法都是O(1)有用的！它是以一种对具体情况有意义的方式应用数学。

以下是您的示例的两种上下文，一种是有意义的O(1)，另一种是没有意义的。

1. “我决定不会将长度超过 15 的字符串放入我的程序中，因此它是O(1)”。这不是对运行时的超级有用的解释。实际时间仍然与绳子的大小密切相关；即使技术上存在常数限制，大小为 1 的字符串也会比大小为 15 的字符串运行得快得多。换句话说，在您的问题的限制范围内，仍然与 存在很强的相关性n。
2. “我的算法将处理一个字符串列表n，每个字符串的最大大小为 15”。这里我们有一个不同的故事；运行时主要是必须运行列表！有一个点n是如此之大以至于处理单个字符串的时间不会改变相关性。现在考虑处理单个字符串的时间O(1)以及处理整个列表的时间是有意义的O(n)

也就是说，Big-O 表示法不必只使用一个变量！存在上限是算法固有的问题，但您不会任意对输入设置上限。相反，您可以将输入的每个维度描述为不同的变量：

n = list length
s = maximum string length
=> O(n*s)

Answer 3

这取决于。

如果提供更大的输入，算法的要求会增加，那么算法复杂性可以（并且应该）独立于输入进行评估。因此，迭代列表、数组、字符串等的所有元素O(n)与输入的长度有关。

如果您的算法与有限的输入大小相关，那么这一事实就会成为您算法复杂性的一部分。例如，也许您的算法仅迭代输入字符串的前 15 个字符，无论它有多长。或者，您的业务案例可能只是表明较大的输入表明调用代码中存在错误，因此只要输入大小大于固定数字，您就选择立即退出并出现错误。在这些情况下，由于输入长度趋于非常大的数字，算法将具有恒定的要求。

来自维基百科

大 O 表示法是一种数学表示法，描述函数在参数趋于特定值或无穷大时的极限行为。
...
在计算机科学中，大 O 表示法用于根据算法的运行时间或空间需求如何随着输入大小的增长而增长来对算法进行分类。

实际上，几乎所有输入都有限制：您不能输入大于数字类型可表示的数字，也不能输入大于可用内存空间的字符串。因此，说任何限制都会改变算法的渐近复杂度都是愚蠢的。理论上，您可以使用 15 作为渐近线（或“特定值”），因此使用 Big-O 表示法来定义算法如何随着输入接近该大小而增长。有些算法具有如此可怕的复杂性（或者某些执行环境的资源有限），这将是有意义的。

但是，如果您的参数（字符串长度）对于算法复杂性的某些方面来说没有趋向于足够大的值来定义其资源需求的增长，则可以说根本不适合使用渐近符号。

Answer 4

不！

算法的时间复杂度与程序约束无关。这是（一种简单的）思考方式：

假设您的算法迭代字符串并将所有辅音附加到列表中。

现在，迭代时间复杂度为 O(n)。这意味着所花费的时间将大致与字符串长度的增加成比例地增加。（时间本身会根据 if 语句和分支预测所花费的时间而变化）

事实上，您知道字符串的长度在 1 到 15 个字符之间，这不会改变程序的运行方式，它只是告诉您会发生什么。

例如，知道您的值将小于 65000，您可以将它们存储在 16 位整数中，而不必担心整数溢出。