但O（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？

我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。

我无法理解如何用对数来识别函数时间

对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。

对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。

这个问题已经有了很多好的答案，但我相信我们真的错过了一个重要的答案，那就是图解的答案。

说一个完整的二叉树的高度是O（logn）是什么意思？

下图描述了一个二叉树。请注意，与上面的级别相比，每个级别包含的节点数量是两倍（因此是二进制的）：

二进制搜索是一个复杂度为O（logn）的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法，图中显示了我们需要（最多）4次比较才能找到我们在这个16项数据集中搜索的记录。

假设我们有一个包含32个元素的数据集。继续上面的图，发现我们现在需要5次比较才能找到我们正在搜索的内容，因为当我们乘以数据量时，树只增长了一层。结果，该算法的复杂性可以用对数级数来描述。

在一张普通纸上绘制对数（n）将生成曲线图，其中曲线的上升速度随着n的增加而减慢：

实际上，如果您有一个n个元素的列表，并从该列表中创建一个二叉树（就像在除法和征服算法中一样），您将一直除以2，直到达到大小为1的列表（树叶）。

在第一步，你除以2。然后，您有2个列表（2^1），将每个列表除以2，因此您有4个列表（2*2），然后再进行一次除法，您有8个列表（3^3），依此类推，直到列表大小为1

这给出了一个等式：

n/（2^步）=1<=>n=2^步<=>lg（n）=步

（取每边的lg，lg为对数基数2）

如果你在图形计算器或类似的东西上绘制一个对数函数，你会发现它的上升速度非常慢——甚至比线性函数还要慢。

这就是为什么对数时间复杂度算法备受追捧的原因：即使对于真正大的n（例如，假设n＝10^8），它们的性能也超出了可接受的范围。

我想补充一点，树的高度是从根到叶的最长路径的长度，节点的高度是该节点到叶的最大路径的长度。路径表示在两个节点之间遍历树时遇到的节点数。为了实现O（logn）时间复杂度，树应该是平衡的，这意味着任何节点的子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。

你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。

每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。

渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。

因为时间复杂度取决于各种参数。1.物理系统2.编程语言3.编码样式4.还有更多。。。。。。

实际执行时间不是一个很好的分析指标。

相反，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的。因此，执行时间是输入大小的函数。

以下是线性时间算法的示例

线性搜索给定n个输入元素，要搜索数组中的元素，最多需要“n”个比较。换句话说，无论你使用什么编程语言，你喜欢什么编码风格，在什么系统上执行它。在最坏的情况下，它只需要n次比较。执行时间与输入大小成线性比例。

它不仅仅是搜索，无论是什么工作（增量、比较或任何操作），它都是输入大小的函数。

所以当你说任何算法都是O（logn）这意味着执行时间是输入大小n的log倍。

随着输入大小的增加，完成的工作（这里是执行时间）增加。（因此，比例）

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

随着输入大小的增加，所做的工作也会增加，并且与任何机器无关。如果你试图找出工作单位的价值它实际上取决于上述参数。它会根据系统和所有参数而改变。