O(logn) + O(n) 是什么意思？

Question

有人告诉我，我的代码应该遵循O(logn)+O(n)的复杂度指南。在要求澄清时，他只回答："代码的复杂度 :)"。无论如何，如果能提供更多的解释，我将不胜感激。

- Benjamin Powers

---

O（log n）+ O（n）= O（n），因此我猜某个人指的是特定算法的组合或给定算法的某些部分（如果有这样）。 - Gabriel Ščerbák

Answer 1

O(logn) + O(n) = O(n)

"有人告诉我，我的代码应该遵循 O(logn) + O(n) 的复杂度准则。" - 如果不知道您的代码应该做什么，没有人能够回答它的合理复杂度应该是什么。请参考大O符号。

- Mitch Wheat

---

不错！链接带我去了https://dev59.com/wHE95IYBdhLWcg3wEpro，提供了适当的上下文。我正在使用array_key_exists和in_array来解决编程谜题。我仍然不确定他/她试图解决什么问题（即这个复杂度是针对数组还是整个应用程序）。我还在https://dev59.com/-HRB5IYBdhLWcg3w3K0J#487278中看到0(log n)表示对数复杂度，在电话示例中，似乎与数组相关。 - Benjamin Powers

Answer 2

没有上下文的情况下，这个问题很难回答。 "O(logn) + O(n)"本身并没有太大意义，因为任何给定算法的渐近复杂度都会被线性项所支配，所以写上"+ O(logn)"并不能澄清任何事情。

- pg1989