Big O复杂性可以有多个答案吗？

Question

您如何谈论Big O复杂性方面的以下功能？

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

在这种情况下，我会看到最坏的情况是O（n）我可以安全地忽略它的O（n ^ 2）值小于10的事实，因为它远离“最坏”的情况。

为了更真实的世界体验。让我们来谈谈查找两个字符串是否相互排列的大小复杂性。这样做的简单方法是为所有字符值取一个整数数组（ascii字符为128）。

现在，如果你切换到一个向量或hashmap（我会说只使用一个整数数组，但有人使用的例子是一个hashmap），你可以得到最多128个字符的可变大小。

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

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

Answer 1

可以有多个答案吗？

是的，大O符号表示类似“小或相等”的东西，所以如果你的努力在O（n）中，它也在O（n log n）或O（n ^ 2）中。然而，人们通常对紧密的约束感兴趣。

让我们来谈谈查找两个字符串是否相互排列的大小复杂性

字符串中可能的字符集是有限的，因此大小复杂度为O（1）。根据我之前所说的，它也在O（n）中;但更严格的界限是O（1）。

Answer 2

您的帖子中有几个问题。而且，它们并不是真正的编程问题。我会尝试一个有用的答案：

循环是在O(n)和O(n^2)（请阅读Big-Oh的定义，例如维基百科）。如果你愿意，循环也可以是O(n^3)或O(n^4)。但这个想法是找到可能的“最低”的O(f(n))，在你的情况下是O(n)，更精确的O(10*n)，这与O(n)真的相同。

算法的增长顺序（或复杂性，如果需要）是其输入大小的函数。那么在你的情况下，彼此是两个字符串排列吗？它取决于字符串的大小。假设最小字符串的大小是n，并且你必须读取决策问题的整个输入，你至少有n步骤（这表明它不能是O(1)）。

哈希映射数组的有限大小是算法内存增长的顺序（空间复杂度），如果你只使用ASCII集，那么我也可以看到它也是O(1)。