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

Question

任何人都可以帮助我了解如何识别给定的代码片段是否是对数时间？我似乎无法理解这个概念。谢谢。

-一个例子就很好了。

Answer 1

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

---

示例:

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

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