假设我们有一串唯一的 ASCII 字符，这意味着它的长度永远不会超过 128 个字符。
如果我要扫描这个字符串，其中扫描意味着对每个字符执行恒定时间操作，那么这次扫描算作O(n)还是O (1)?
其中n是字符串的实际长度。
最佳答案
答案
当询问算法的时间或空间复杂度(以 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)那么好，但它现在是一个通用算法，可以用于任何输入大小，而不是我们将输入限制作为算法本身的一部分。
关于big-o - 扫描有限长度字符串的复杂性。 O(n) 还是 O(1)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53100130/