big-o - 扫描有界长度字符串的复杂性。O(n) 还是 O(1)？

Question

假设我们有一串唯一的 ASCII 字符，这意味着它的长度永远不会超过 128 个字符。

如果我要扫描这个字符串，其中扫描意味着对每个字符执行恒定时间操作，那么这个扫描算作 O(n) 还是 O(1)？

其中n是字符串的实际长度。

标签： big-ocomplexity-theoryanalysis

Answer 1

答案

当根据 询问算法的时间或空间复杂度时n，您需要定义什么n是。

n如您所知，对字符数组进行线性扫描的时间复杂度为O(n). 由于您将相同的算法应用于 <= 128 个字符的数组，因此您绝对可以正确地说您正在将O(n)算法应用于数组。

但是，如果您将算法定义为“扫描最多 128 个字符的字符数组”，那么您的算法确实具有时间复杂度，O(1)因为它的操作数上限为常数。

所以回答你的问题：这是一个观点问题。你如何定义你的算法？

• “长度数组的广义扫描n”？然后是O(n)，n在您的特定应用程序中恰好永远不会超过 128（对您有好处）。
• “扫描 128 个或更少字符”？那么它是O(1)，因为它的时间上限是一个常数。

哲学再深一点

现在，即使您要扩展数组的长度以填满所有 RAM，但它仍然是一个有限整数，因此您在数学上完全正确地声称它会O(1)及时运行。然而！定义一个扫描适合您的 RAM 的数组的算法有多重要？我们刚刚严重降低了算法的实用性，因为如果说我的 RAM 比你多，那么你的算法将无法满足我的需求。

这就是为什么我们使用参数 ,n来表示一些度量（这里是数组的长度）。这允许我们定义一个适用于任何（！）大小的输入的扫描算法。如您所知，此算法充其量是O(n)，听起来可能不如O(1)，但它现在是一种通用算法，可用于任何输入大小，而不是我们将输入限制作为算法本身的一部分.