当最坏情况下的数值已知时

Question

如果我有一个算法，其中的一部分有一个已知的最坏情况数值，与问题的其他部分相比，它是相当小的，它可以作为O(1)来争论吗？

例如，如果算法的一部分涉及从字符串中构建一个链接的字符列表，其中的字符串最多一次包含每个ASCII字符，我知道最糟糕的情况是从127个字符长的字符串构建一个包含127个节点的链接列表。把这部分作为O(1)来争论可以吗？

Answer 1

是的，一旦知道一个绝对上界，该算法就具有恒定的复杂性。

算法的复杂性只关心算法如何对任意大的输入大小进行缩放:对于10,000和1万亿个元素，需要多长时间？因为您的算法只定义到某个最大的大小，所以这种缩放不是很相关的。

在分析大O复杂度时，这种最大输入参数通常非常方便.例如，我们通常假设乘法和加法是O(1)运算。但这只适用于固定宽度的数据类型，而这些数据类型在实践中往往是足够的。它不适用于任意精度/大型操作，其中加法将具有O(log )复杂性(或O(n)位数)。

即使有一个最大的大小，完全忽略大O也不总是可以的。如果该算法在其定义的域内显示显着的缩放属性，则应对其进行分析。例如，O(exp n)算法可能在任何情况下都是不可行的，只有一位数的输入大小，所以几千个上限是完全不相关的，因为它永远不会达到。同样，所有程序都是O(1)，因为真正的计算机有有限的内存，因此是有界的，这种说法是似是而非的:在达到这个极限之前，你通常会感觉到大O的影响。

Answer 2

不，我不接受对可能输入的(低)限制作为调用该部分O(1)的一个参数。

另一方面，如果这是对最坏情况输入没有相同限制的更大算法的一部分，那么整个算法是O(f(N)*g(M))，其中f(N)是具有有界最坏情况输入的部分的复杂性，而g(M)是另一部分的复杂性。

现在可以认为，对于大M，g(M)部分控制着整体的复杂性，而有界输入部分的影响可以忽略不计，以便进一步分析。

Answer 3

这取决于谁在读这篇文章。计算机科学通常关注渐近情况。但是在您的例子中，您似乎有O (n)，其中n是可能的不同字符的数目，并且通过选择ASCII并声称它是O (1)，人为地将n限制为128。嗯，我想至少处理完整的Unicode范围(大约100万个代码点)，并且可能是扩展的图形素集群，它们是无限的，所以我会发现这是非常不令人满意的。

在软件工程中，我们通常关注它在实践中的运行速度。如果您执行k操作，并且每个操作都是超过128个ASCII字符的循环，这将对运行时产生影响，人们可能会认为您作弊。