什么是O（log n）的意思是什么呢？ [英] What does O(log n) mean exactly?

问题描述

我目前了解大O符号的运行时间和摊销次。我理解的概念的 O（N）的线性时间，这意味着输入的大小影响算法按比例的增长... ...和同样的，例如，二次时间的为O（n ² ）的etc..even算法，如置换发电机，用的 O（N！）的时候，生长受阶乘。

例如，下面的功能的 O（N）的，因为在算法中的比例增大到其输入的 N 的：

  F（INT N）{
  INT I;
  对于（I = 0; I＆n种++ⅰ）
    的printf（％D，我）;
}
 

同样，如果有一个嵌套循环，时间将是为O（n ² ）。

但究竟什么是的 O（log n）的的？例如，这是什么意思是说，一个完全二叉树的高度的 O（log n）的的？

我知道（也许不是很详细）什么对数，在这个意义上：登录 ₁₀ 100 = 2，但我不明白如何识别功能，具有对数时间

解决方案

  

我不明白如何识别功能，具有对数时间。

对数运行时函数中最常用的属性是：

• 在其上执行一些动作的下一个元素的选择是一个几种可能性，和
• 将需要选择只有一个。

或

• 在其上执行操作的元件为n的位

这是为什么，例如，寻找达人的电话本是O（log n）的。你并不需要检查的每次的人在电话簿中找到合适的人;相反，你可以简单地分而治之，而你只需要探索整个空间的一小部分，然后最终找人的电话号码。

当然，更大的电话簿仍然会花费你很长的时间，但它不会成长为尽快在更多的大小比例增加。

---

我们可以展开电话簿的例子来比较其他类型的操作和的的运行时间。我们假设我们的电话簿具有的企业的（以下简称黄​​页），它具有独特的名字和的个人的（以下简称白页），这可能不具有唯一的名称。一个电话号码分配给至多一个个人或企业。我们还假设，它需要一定的时间翻转到一个特定的页面。

下面是一些操作的运行时间，我们可以对电话簿进行，从最好到最差的：

• O（1）（最坏情况下）：由于网页，一个企业的名字是和企业名称，发现该电话号码

• O（1）（一般情况）：由于网页，一个人的名字是和他们的名字，发现该电话号码

• O（log n）的：由于一个人的名字，发现手机号码通过拾取随机点约一半您还没有搜索到这本书的一部分，然而，再检查看看是否这个人的名字是在这一点上。然后通过本书，这个人的名字就在于部分重复大约一半的过程。 （这是一个二进制搜索的人的名字。）

• O（N）：查找所有的人，他们的电话号码包含的数字5

• O（N）：给定一个电话号码，发现此人或企业与该号

• 为O（n log n）的：有一个混淆在打印机的办公室，和我们的电话本有它的所有页面以随机顺序插入。修复顺序，以便它是正确的通过查看每个页面上的第一个名字，然后把该页面在适当的地点在一个新的，空的电话簿。

对于下面的例子，我们现在是在打印机的办公室。电话簿正在等待邮寄给每个居民或企业，并有每个电话簿的标签识别它应该被邮寄到。每个人或企业得一电话本。

• 为O（n log n）的：我们想要个性化电话簿，所以我们会发现每个人或企业的名字在他们指定的副本，再绕在他们的名字这本书，写一个简短的感谢信，对他们的光顾。

• 为O（n ² ）：：一种错误发生在办公室，并在每个电话簿中的每个条目有一个额外的0的的电话号码结束。就拿一些白色的淘汰和删除每个零。

• 为O（n＆middot; N！）：：我们已经准备好加载通讯录到货运码头。不幸的是，这应该加载书籍机器人已经失控的：它把书籍到卡车以随机顺序！更糟糕的是，它加载所有的书上卡车，然后检查他们是否在正确的顺序，如果没有，它卸载它们，然后重新开始。 （这是可怕的 BOGO排序 。）

• 为O（n ^N ）：您修复机器人，以便它的正确加载的东西。第二天，你的同事之一，扮演一个恶作剧你和电线装卸码头机器人自动打印系统。每次机器人去加载原书，工厂打印机，使所有的通讯录的副本跑！幸运的是，机器人的错误检测系统足够复杂的机器人不会尝试打印更加副本遇到一个重复的书时加载，但它仍然需要装入每个正本和副本的书，是被打印出来。

I am currently 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.

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);
}

Similarly, if there was a nested loop, the time would be O(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)?

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:

• 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

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, and you only need to explore a tiny fraction of the entire space 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) (worst case): Given the page that a business's name is on and the business name, find the phone number.

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

• 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): Find all people whose phone numbers contain the digit "5".

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

• 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): 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²): 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!): 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ⁿ): 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屋！