假设我们有一个唯一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来表示某种度量(这里是数组的长度(。此允许我们定义适用于ANY(！(大小输入的扫描算法。正如你所知，这个算法充其量是O(n)，听起来可能不如O(1)好，但它现在是一个通用算法，可以用于任何输入大小，而不是我们将输入限制作为算法本身的一部分。
一方面，它是O(n(，因为程序的复杂性取决于某个变量n，该变量可以在[0128]的范围内改变宽度。
另一方面，如果程序总是进行相同数量的操作，则会得到O(1(。事实并非如此，因为如果它的长度越大，就需要做更多的工作。
尽管考虑到最坏的情况是O(128(，因此使其成为O(1(