扫描有界长度字符串的复杂性。 O(n) 还是 O(1)？
Complexity of scanning a bounded length string. O(n) or O(1)?
假设我们有一串 唯一的 ASCII 字符，这意味着它的长度永远不会超过 128 个字符。
如果我要扫描这个字符串，其中 扫描 意味着对每个字符执行 constant-time 操作，这次扫描算不算作为 O(n) 或 O(1)?
其中n是字符串的实际长度。
一方面它是 O(n)，因为程序的复杂性取决于某个变量 n，它可以在 [0, 128] 范围内改变宽度。
另一方面，如果程序总是进行相同数量的操作，那么您的复杂度为 O(1)。事实并非如此，因为如果它的长度更大，则需要更多的工作。
尽管考虑到最坏的情况是 O(128) 因此使其成为 O(1)
答案
当根据 n 询问算法的时间或 space 复杂度时，您需要定义 n 是什么。
如您所知，n 个字符数组的线性扫描具有 O(n) 的时间复杂度。由于您将相同的算法应用于 <= 128 个字符的数组，因此您可以肯定地说您正在对数组应用 O(n) 算法。
但是，如果你将算法定义为"scanning through a character array of max 128 characters"，那么你的算法确实会有O(1)的时间复杂度，因为它的操作数上限是一个常数。
所以回答你的问题：这是一个角度问题。你如何定义你的算法？
- "A generalized scan of an array of length
n"？然后是 O(n)，其中 n 在您的特定应用程序中恰好不会超过 128（对您有好处）。
- "A scan of 128 or fewer characters"？然后是
O(1)，因为它的时间上限是一个常数。
进一步思考
现在，即使您要扩展数组的长度以填满所有 RAM，无论多大，它仍然是一个有限整数，因此从数学上讲，您声称它将 运行 在 O(1) 时间内。 但是！定义一个算法来扫描适合您的 RAM 的数组有多重要？我们刚刚严重削弱了我们算法的实用性，因为如果，比方说，我的 RAM 比你多，那么你的算法将无法满足我的需求。
这就是为什么我们使用参数 n 来表示一些度量（这里是数组的长度）。这 允许 我们定义一个适用于任何（！）大小输入的扫描算法。如您所知，此算法充其量是 O(n)，听起来可能不如 O(1)，但它现在是一种通用算法，可用于任何输入大小，而不是我们使用的算法将输入限制作为算法本身的一部分。
假设我们有一串 唯一的 ASCII 字符，这意味着它的长度永远不会超过 128 个字符。
如果我要扫描这个字符串，其中 扫描 意味着对每个字符执行 constant-time 操作，这次扫描算不算作为 O(n) 或 O(1)?
其中n是字符串的实际长度。
一方面它是 O(n)，因为程序的复杂性取决于某个变量 n，它可以在 [0, 128] 范围内改变宽度。
另一方面，如果程序总是进行相同数量的操作，那么您的复杂度为 O(1)。事实并非如此，因为如果它的长度更大，则需要更多的工作。
尽管考虑到最坏的情况是 O(128) 因此使其成为 O(1)
答案
当根据 n 询问算法的时间或 space 复杂度时，您需要定义 n 是什么。
如您所知，n 个字符数组的线性扫描具有 O(n) 的时间复杂度。由于您将相同的算法应用于 <= 128 个字符的数组，因此您可以肯定地说您正在对数组应用 O(n) 算法。
但是，如果你将算法定义为"scanning through a character array of max 128 characters"，那么你的算法确实会有O(1)的时间复杂度，因为它的操作数上限是一个常数。
所以回答你的问题：这是一个角度问题。你如何定义你的算法？
- "A generalized scan of an array of length
n"？然后是O(n)，其中n在您的特定应用程序中恰好不会超过 128（对您有好处）。 - "A scan of 128 or fewer characters"？然后是
O(1)，因为它的时间上限是一个常数。
进一步思考
现在，即使您要扩展数组的长度以填满所有 RAM，无论多大，它仍然是一个有限整数，因此从数学上讲，您声称它将 运行 在 O(1) 时间内。 但是！定义一个算法来扫描适合您的 RAM 的数组有多重要？我们刚刚严重削弱了我们算法的实用性，因为如果，比方说，我的 RAM 比你多，那么你的算法将无法满足我的需求。
这就是为什么我们使用参数 n 来表示一些度量（这里是数组的长度）。这 允许 我们定义一个适用于任何（！）大小输入的扫描算法。如您所知，此算法充其量是 O(n)，听起来可能不如 O(1)，但它现在是一种通用算法，可用于任何输入大小，而不是我们使用的算法将输入限制作为算法本身的一部分。