algorithm - 如何识别代码片段的Big-O Notation是否为对数时间O(logn)？

Question

谁能帮助我理解如何识别给定代码片段是否为对数时间？我似乎无法理解这个概念。谢谢。

-举个例子就好了。

Answer 1

如果您将输入分成等长或几乎等长的部分，然后仅在输入的一部分中继续您的操作(搜索、排序等)，那么您的代码将受 Log (n) 约束。

---

例子:

1. 对排序数组进行二进制搜索:在这里，您将输入数组分成两部分，然后仅在其中的一部分继续搜索。复杂度为 O(Log₂(n))。

2. 搜索 m 路树:这里您的节点有 m 条路径。您可以从这 m 条路径中选择一条，然后沿着树继续搜索。复杂度为 O(Log_m(n))。