在复杂度理论中，O(lg(n)) * O(lg(n)) 表示为对数阶乘级别。

Question

在复杂度问题上卡住了。

我有一个运行时间为 O(lg(n)) 的循环。我还有另一个嵌套在其中的循环，也是 O(lg(n))，因此整个复杂度为 O(lg(n)) * O(lg(n)) 或者 O(lg(n)²)。我能否说最终的复杂度为 O(lg(n))，因为 n 是 2 的幂次方，所以

O(lg(n)) * O(lg(n)) = O(lg(n²))=O(2lg(n))=O(lg(n))

或者不能这样使用？

- Boltosaurus

---

它的时间复杂度为O(lg(n)^2)!! - Blackhat002

Answer 1

不，你不能这样做！因为这个原因:

O(lg(n)) * O(lg(n)) = O(lg(n²))

是不正确的。尽管其余部分是正确的，所以你的循环仍然是O(lg(n)²)

- Lrrr

---

谢谢，这正是我所想的。 - Boltosaurus

@Boltosaurus 不用谢 :) 如果有帮助，请不要忘记将其标记为答案。 - Lrrr