这两种情况需要O（log n）时间

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

简单地说：在算法的每一步，你都可以将工作减半。（渐近等价于第三、第四、…）

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

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

因为时间复杂度取决于各种参数。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

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

O（logn）指的是一个函数（或算法，或算法中的步骤），其工作时间与输入大小的对数成正比（大多数情况下通常以2为基数，但并不总是以2为底，在任何情况下，通过big-O符号*，这都是无关紧要的）。

对数函数是指数函数的倒数。换句话说，如果您的输入呈指数增长（而不是通常认为的线性增长），则函数呈线性增长。

O（logn）运行时间在任何一种分而治之的应用程序中都很常见，因为（理想情况下）每次都会将工作减半。如果在每一个除法或征服步骤中，你都在做恒定时间的工作（或不是恒定时间的，但随着时间的增长比O（log n）慢），那么你的整个函数就是O（log）。相当常见的是，每个步骤都需要输入线性时间；这将相当于O（n log n）的总时间复杂度。

二进制搜索的运行时间复杂性是O（logn）的一个例子。这是因为在二进制搜索中，通过将数组分成两半，并且每一步只关注一半，您总是忽略后面每一步的一半输入。每一步都是恒定的时间，因为在二进制搜索中，您只需要将一个元素与关键字进行比较，就可以确定下一步要做什么，而不管您考虑的数组在任何时候都有多大。因此，大约执行log（n）/log（2）步。

合并排序的运行时间复杂性是O（n log n）的一个例子。这是因为每一步都将阵列一分为二，总共约为log（n）/log（2）步。然而，在每一步中，您都需要对所有元素执行合并操作（无论是对n/2个元素的两个子列表执行一次合并操作，还是对n/4个元素的四个子列表执行两次合并操作都是无关紧要的，因为这增加了每一步对n个元素执行合并的必要性）。因此，总复杂度为O（n log n）。

*记住，根据定义，big-O表示法并不重要。同样，通过改变对数的基数规则，不同基数的对数之间的唯一差异是一个常数因子。

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

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

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

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