algorithm - Big O 的复杂性可以有不止一个答案吗？

Question

您如何从 Big O Complexity 的角度谈论以下函数？

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n && j < 10; j++) {
    //do something in constant time
  }
}

在这种情况下，我会看到最坏的情况是 O(n) 我是否可以放心地忽略它对于小于 10 的值是 O(n^2) 这一事实，因为它远非“最坏”的情况。

为了获得更真实的体验。让我们来谈谈查找两个字符串是否互为排列的大小复杂度。实现它的简单方法是为所有字符值取一个整数数组(ascii 字符为 128)。

现在，如果您切换到向量或散列图(我会说只使用整数数组，但有人使用的示例是散列图)，您将输入最多 128 个字符的可变大小。

我们正在讨论大小复杂度，我只是说它是 O(1) 只是因为在最坏的情况下你会得到 128。另一个人自信地说它是 O(n) 最多 128 个字符，并成为O(1) 的限制。我们没有确定的答案。

我从未听说过在与 Big O 打交道时使用“限制”。那么在这种情况下哪个是正确的？我是否正确，判断大 O 时的正确复杂性仅在 n 是“足够大”时才被考虑？还是有其他情况可以有替代答案？

Answer 1

Can there be more than one answer?

是的，大 O 表示法表示“小于或等于”之类的东西，因此如果您的工作量在 O(n) 中，它也在 O(n log n) 或 O(n^2) 中。然而，人们通常对紧束缚感兴趣。

Let's talk about the size complexity of finding if two strings are permutations of each other

字符串中可能的字符集是有限的，因此大小复杂度为 O(1)。结合我前面说的，也是在O(n)；但更严格的界限是 O(1)。