O(log n) 到底是什么意思? [英] What does O(log n) mean exactly?

问题描述

我正在了解 Big O Notation 运行时间和摊销时间.我理解 O(n) 线性时间的概念，这意味着输入的大小会按比例影响算法的增长……例如，二次时间 也是如此O(n²) 等等.甚至算法，例如置换生成器，具有 O(n!) 次，通过阶乘增长.

I am learning about Big O Notation running times and amortized times. 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)，因为算法的增长与其输入成比例n:

For example, the following function is O(n) because the algorithm grows in proportion to its input n:

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

同样，如果有嵌套循环，时间也是 O(n²).

Similarly, if there was a nested loop, the time would be O(n²).

但是O(log n)究竟是什么?例如，完全二叉树的高度是O(log n)是什么意思?

But what exactly is O(log n)? For example, what does it mean to say that the height of a complete binary tree is O(log n)?

我确实知道(可能不是很详细)对数是什么，从某种意义上说:log₁₀ 100 = 2，但我无法理解如何识别具有对数时间的函数.

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.

推荐答案

我无法理解如何使用日志时间识别函数.

I cannot understand how to identify a function with a log time.

对数运行时函数最常见的属性是:

The most common attributes of logarithmic running-time function are that:

• 选择下一个要执行某些操作的元素是多种可能性之一，并且
• 只需要选择一个.

或

• 执行动作的元素是 n 的数字

这就是为什么，例如，在电话簿中查找人员是 O(log n).你不需要检查电话簿中的每个人来找到合适的人；相反，您可以通过根据姓名的字母顺序查找来简单地进行分而治之，并且在每个部分中，您只需要探索每个部分的一个子集，就可以最终找到某人的电话号码.

This is why, for example, looking up people in a phone book is 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 fastest to slowest:

• O(1)(在最坏的情况下):根据企业名称所在的页面和企业名称，找到电话号码.

• O(1) (in the worst case): Given the page that a business's name is on and the business name, find the phone number.

O(1)(一般情况下):给定一个人的名字所在的页面和他们的名字，找到电话号码.

O(1) (in the average case): Given the page that a person's name is on and their name, find the phone number.

O(log n): 给定一个人的名字，在你还没有搜索过的书的大约一半的地方随机选择一个点来找到电话号码，然后检查看看那个人的名字是否在那个点上.然后在本书中该人姓名所在的部分重复该过程.(这是对人名的二分搜索.)

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. 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):找出所有电话号码包含数字5"的人.

O(n): Find all people whose phone numbers contain the digit "5".

O(n):给定一个电话号码，找出拥有该号码的个人或企业.

O(n): Given a phone number, find the person or business with that number.

O(n log 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. 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):我们想要个性化电话簿，所以我们要在他们指定的副本中找到每个人或企业的名字，然后圈出他们的名字并为他们的惠顾写一封简短的感谢信.

• 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²): 办公室发生了一个错误，每本电话簿中的每一个条目都有一个额外的0"电话号码的结尾.取一些白色并删除每个零.

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. Take some white-out and remove each zero.

O(n · n!):我们已准备好将电话簿加载到装运码头.不幸的是，本应装载书籍的机器人已经失控了:它以随机顺序将书籍放到卡车上！更糟糕的是，它会将所有书籍装载到卡车上，然后检查它们的顺序是否正确，如果不是，则卸载它们并重新开始.(这是可怕的bogo sort.)

O(n · n!): We're ready to load the phonebooks onto the shipping dock. 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.)

O(nⁿ):你修复了机器人，让它正确装载东西.第二天，您的一位同事对您恶作剧，并将装卸台机器人连接到自动打印系统.每次机器人去加载一本原始书籍时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统足够复杂，当遇到要加载的重复书籍时，机器人不会尝试打印更多副本，但它仍然必须加载已打印的所有原始和重复书籍.

O(nⁿ): You fix the robot so that it's loading things correctly. 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.

这篇关于O(log n) 到底是什么意思?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！