algorithm - 大O复杂性是否可以有多个答案？

在大O复杂度方面，你会如何谈论下面的函数？

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）。
现在，如果切换到向量或hashmap（我想说只是使用整数数组，但有人使用的示例是hashmap），则输入的变量大小最多可达128个字符。
我们在讨论尺寸的复杂性，我只是说它是O（1），因为最坏的情况下你会得到128。另一个人自信地说，它是O（n）最多128个字符，并成为O（1）的限制我们没有确切的答案。
我从来没有听说过在处理大O时使用“限制”。那么在这种情况下哪个是正确的呢？我是正确的吗？判断大O的正确的复杂性只是在N足够大的时候才会被考虑吗？或者还有其他情况下可以有替代答案吗？

最佳答案

能有不止一个答案吗？
是的，大o符号表示类似于“较小或相等”的东西，所以如果你的努力在o（n）中，它也在o（n logn）或o（n^2）中。然而，人们通常对紧束缚感兴趣。
让我们来讨论一下如果两个字符串是相互置换的大小复杂性。
字符串中的可能字符集是有限的，因此大小复杂度在O（1）中。根据我之前所说的，它也在o（n）中；但是更紧的界限是o（1）。

关于algorithm - 大O复杂性是否可以有多个答案？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54865964/