time-complexity - O（log n）究竟意味着什么？(What does O(log n) mean exactly?)

Question

I am learning about Big O Notation running times and amortized times. (我正在学习Big O Notation运行时间和摊销时间。) I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportionally...and the same goes for, for example, quadratic time O(n ² ) etc..even algorithms, such as permutation generators, with O(n!) times, that grow by factorials. (我理解O（n）线性时间的概念，意味着输入的大小成比例地影响算法的增长...例如，二次时间O（n ² ）等也是如此。即使算法也是如此。 ，例如置换生成器，具有O（n！）倍，通过阶乘生长。)

For example, the following function is O(n) because the algorithm grows in proportion to its input n : (例如，以下函数是O（n），因为算法与其输入n成比例增长：)

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Similarly, if there was a nested loop, the time would be O(n ² ). (同样，如果有嵌套循环，则时间为O（n ² ）。)

But what exactly is O(log n) ? (但究竟什么是O（log n） ？) For example, what does it mean to say that the height of a complete binary tree is O(log n) ? (例如，说完整二叉树的高度是O（log n）是什么意思？)

I do know (maybe not in great detail) what Logarithm is, in the sense that: log ₁₀ 100 = 2, but I cannot understand how to identify a function with a logarithmic time. (我知道（可能不是非常详细）什么是对数，在这个意义上：log ₁₀ 100 = 2，但我无法理解如何识别具有对数时间的函数。)

  ask by Andreas Grech translate from so

Answer 1

I cannot understand how to identify a function with a log time. (我无法理解如何识别具有日志时间的函数。)

The most common attributes of logarithmic running-time function are that: (对数运行时函数最常见的属性是：)

• the choice of the next element on which to perform some action is one of several possibilities, and (选择下一个要执行某些操作的元素是几种可能性之一，并且)
• only one will need to be chosen. (只需要选择一个。)

or (要么)

• the elements on which the action is performed are digits of n (执行动作的元素是n的数字)

This is why, for example, looking up people in a phone book is O(log n). (这就是为什么，例如，在电话簿中查找人是O（log n）。) You don't need to check every person in the phone book to find the right one; (您无需检查电话簿中的每个人以找到合适的人;) instead, you can simply divide-and-conquer by looking based on where their name is alphabetically, and in every section you only need to explore a subset of each section before you eventually find someone's phone number. (相反，您可以通过基于字母顺序查看其名称来简单地分而治之，并且在您最终找到某人的电话号码之前，您只需在每个部分中探索每个部分的子集。)

Of course, a bigger phone book will still take you a longer time, but it won't grow as quickly as the proportional increase in the additional size. (当然，更大的电话簿仍然会花费更长的时间，但它不会像额外的大小成比例增长那么快。)

---

We can expand the phone book example to compare other kinds of operations and their running time. (我们可以扩展电话簿示例，以比较其他类型的操作及其运行时间。) We will assume our phone book has businesses (the "Yellow Pages") which have unique names and people (the "White Pages") which may not have unique names. (我们将假设我们的电话簿中有商家 （“黄页”），这些商家具有唯一的名称和人员 （“白页”），这些商家可能没有唯一的名称。) A phone number is assigned to at most one person or business. (电话号码最多分配给一个人或企业。) We will also assume that it takes constant time to flip to a specific page. (我们还假设需要一段时间才能翻到特定页面。)

Here are the running times of some operations we might perform on the phone book, from best to worst: (以下是我们可能在电话簿上执行的一些操作的运行时间，从最佳到最差：)

• O(1) (best case): Given the page that a business's name is on and the business name, find the phone number. (O（1）（最佳情况）：给定企业名称所在的页面和企业名称，找到电话号码。)

• O(1) (average case): Given the page that a person's name is on and their name, find the phone number. (O（1）（平均情况）：给出一个人姓名所在的页面及其姓名，找到电话号码。)

• O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. (O（log n）：给定一个人的姓名，通过在您尚未搜索的书的部分中间选择一个随机点来查找电话号码，然后检查该人的姓名是否在该点。) Then repeat the process about halfway through the part of the book where the person's name lies. (然后在书的一部分中间重复这个过程。) (This is a binary search for a person's name.) (（这是对某个人姓名的二进制搜索。）)

• O(n): Find all people whose phone numbers contain the digit "5". (O（n）：查找电话号码包含数字“5”的所有人。)

• O(n): Given a phone number, find the person or business with that number. (O（n）：给定电话号码，找到具有该号码的个人或企业。)

• O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. (O（n log n）：打印机的办公室出现混乱，我们的电话簿的所有页面都是以随机顺序插入的。) Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book. (通过查看每个页面上的第一个名称然后将该页面放在新的空白电话簿中的适当位置来修复排序以使其正确。)

For the below examples, we're now at the printer's office. (对于以下示例，我们现在在打印机的办公室。) Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. (电话簿等待邮寄给每个居民或企业，每个电话簿上都有一个标签，标明应该邮寄到哪里。) Every person or business gets one phone book. (每个人或企业都有一本电话簿。)

• O(n log n): We want to personalize the phone book, so we're going to find each person or business's name in their designated copy, then circle their name in the book and write a short thank-you note for their patronage. (O（n log n）：我们想要个性化电话簿，所以我们将在指定的副本中找到每个人或公司的名字，然后在书中圈出他们的名字并为他们的赞助写一个简短的感谢信。 。)

• O(n ² ): A mistake occurred at the office, and every entry in each of the phone books has an extra "0" at the end of the phone number. (O（n ² ）：办公室发生错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。) Take some white-out and remove each zero. (取一些白色并删除每个零。)

• O(n · n!): We're ready to load the phonebooks onto the shipping dock. (O（n·n！）：我们准备将电话簿加载到装运码头。) Unfortunately, the robot that was supposed to load the books has gone haywire: it's putting the books onto the truck in a random order! (不幸的是，应该装载书籍的机器人已经乱了！它正在以随机的顺序把书放到卡车上！) Even worse, it loads all the books onto the truck, then checks to see if they're in the right order, and if not, it unloads them and starts over. (更糟糕的是，它将所有书籍加载到卡车上，然后检查它们是否按正确顺序排列，如果没有，则将其卸载并重新开始。) (This is the dreaded bogo sort .) (（这是可怕的bogo排序 。）)

• O(n ⁿ ): You fix the robot so that it's loading things correctly. (O（n ⁿ ）：你固定机器人，以便它正确加载东西。) The next day, one of your co-workers plays a prank on you and wires the loading dock robot to the automated printing systems. (第二天，你的一个同事对你进行恶作剧，并将装卸码头机器人连接到自动打印系统。) Every time the robot goes to load an original book, the factory printer makes a duplicate run of all the phonebooks! (每次机器人装载原始书籍时，工厂打印机都会重复运行所有电话簿！) Fortunately, the robot's bug-detection systems are sophisticated enough that the robot doesn't try printing even more copies when it encounters a duplicate book for loading, but it still has to load every original and duplicate book that's been printed. (幸运的是，机器人的错误检测系统足够复杂，以至于当机器人遇到重复的书籍进行加载时，机器人不会尝试打印更多的副本，但它仍然必须加载已打印的每本原始和重复的书籍。)

For more mathematical explanation you can checkout how the time complexity arrives to log n here. (欲了解更多数学上的解释，你可以检出的时间复杂度如何到达log n这里。) https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf (https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf)