n log n实际上是什么意思? [英] What is n log n means practically?

问题描述

大家好，

当我们说Big O是nlonn时，它到底意味着什么.我的确切问题是我们如何正确地理解性能.

在此先感谢

Hi All,

When we say Big O is nlonn, what does it exactly means. My exact question is how we iterprete it performance wise.

Thanks in advance

推荐答案

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

选择要在其上执行某项操作的下一个元素是几种可能性之一，并且只需要选择一个，否则要执行该操作的元素就是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(n2):在办公室发生了一个错误，每个电话簿中的每个条目在电话号码的末尾都有一个额外的"0".进行一些涂白并删除每个零.

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

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

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(n2): 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(nn): 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.

Big-Oh符号具有明确的数学含义.当您说变量N的函数f是N的某些函数g的big-Oh时，这意味着对于所有N，f(N)的上界是C.g(N)的边界[除了可能是第一个值]，其中系数C称为隐藏常数". http://en.wikipedia.org/wiki/Big_O_notation [

The Big-Oh notation has a well-defined mathematical meaning. When you say that a function f of a variable N is big-Oh of some function g of N, it means that f(N) is bounded above by C.g(N) for all N [except maybe for the first values], where the coefficient C is called the "hidden constant". http://en.wikipedia.org/wiki/Big_O_notation[^]

For instance, when you say that a sorting algorithm has running time T(N) = O(N.Log(N)), where N is the number of elements to be processed, that means that the running time grows not faster that N.Log(N).

[Keep in mind that you need to scale these values with the hidden constant, which depends on how precisely the code is written in the innermost loops and how the compiler does its optimization job.]

When an algorithm has linear time behavior O(N), that means that solving the problem is not more complicated than merely stating the problem: just reading the input data takes time O(N). Algorithms with a linlog behavior (O(N.Log(N)) are also considered as fast ones. Things get worse with polynomial times like O(N^2).

N       N.Log(N) N^2
10      33       100
100     664      10000
1000    9966     1000000
10000   132877   100000000
100000  1660964  10000000000
1000000 19931569 1000000000000

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