在实践和理论上，我们在哪里划定 O(1) 和 O(n) 之间的界限？

Question

假设我们有以下问题以及可以提供帮助的 java 方法。

用户输入的密码长度介于 5 个字符和 35 个字符之间（含）。我们需要确保它们不会连续 3 次重复相同的字符。

boolean has3CharsInARow(char [] password){
  for(int left=0, middle=1, right=2; right < password.length; left++, middle++, right++){
    if(password[left]==password[middle] && password[middle]==password[right]){
      return true;
    }
  }
  return false;
}

时间复杂度是多少（为简单起见，假设大 O 表示法和最坏情况）？

我的想法是我们不知道密码中的 3 个字符出现在哪里，所以我们必须搜索所有合适的字符可以肯定的是字符。但是我正在努力 class 将它作为 n 个字符的 O(1) 或 O(n)。

O(1) 的参数是什么？鉴于上下文，我们知道它最多可以限制密码长度为 35 个字符。所以在最坏的情况下，我们找不到 3 个重复的字符，我们扫描 O(34) 33 以找到正确的索引 2 到 34 和 1 个因为当 right 为 35 时，然后我们退出循环守卫，最后 return false。由于 34 是一个常数，所以通常我们说 O(34) = O(1) 是常数时间复杂度。

O(n) 的参数是什么？好吧，我们关心函数的时间效率如何随着输入长度的增长而变化。要是我们假设 T(n) 是 has3CharsInARow 的运行时间，我们可以说 T 与密码长度的每个单位或字符增加成线性比例增长。所以 T 在函数 O(n).

的 class 中

O(1) 和 O(n) 之间的界线在哪里？

编辑：既然一位回答者写了 O(n) 那么这是否意味着这个等效方法也是 O(n)？

boolean has3CharsInARow(char [] password){
  switch(password.length){
    case 0:
    case 1:
    case 2:
        return false;
    case 3: return password[0] == password[1] && password[1] == password[2];
    case 4: return password[0] == password[1] && password[1] == password[2] ||
            password[1] == password[2] && password[2] == password[3];
    ...
    case 35: return ...;

  }
}

Answer 1

算法的时间复杂度为O(n)。这里真的没有回旋余地。这是数学和算法分析。为了完整起见，最好的情况是 O(1)，平均情况和最坏的情况是 O(n)。

我认为混淆来自于人们不理解大 O 符号的含义以及如何解释它。你说（我在解释）："but if I limit the size of the input to a constant, then the complexity is really a constant, no?" 答案是：不。时间复杂度是算法的时间执行如何随着输入的增长而增长的 "description"。即使输入的范围是 [5, 35] 或 [5, Integer.MAX_VALUE] 或 [5, ∞)，此 "description" 仍然成立。它是运行时间和输入大小之间的（共）关系。

时间复杂度不会告诉您算法需要多长时间才能达到运行。它告诉您更改输入大小对运行时间的影响有多大。

让我们看看时间复杂度对您的情况有何帮助：

时间复杂度是线性的。对于这么小的输入大小，你可以得出一个合理的结论，即算法没问题，你不必太担心。

但是，例如，如果您的算法的时间复杂度类似于 O(2^n)，那么这会告诉您运行时间只会爆炸在可能很小的输入尺寸下，您实际上必须查看尺寸 35 是否仍然可以接受。

在实践和理论上，我们在哪里划定 O(1) 和 O(n) 之间的界限？

Where do we draw the line between O(1) and O(n) both in practice and theory?

complexity-theory

time-complexity