Вопрос: Что означает O (log n)?


В настоящее время я изучаю время работы Big O Notation и время амортизации. Я понимаю понятие На) линейное время, что означает, что размер ввода влияет на рост алгоритма пропорционально ... и то же самое касается, например, квадратичного времени На 2 ) и т.д. ... даже алгоритмы, такие как генераторы перестановок, с На!) раз, которые растут факториалами.

Например, следующая функция На) потому что алгоритм растет пропорционально его вводу N :

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

Аналогично, если бы был вложенный цикл, время было бы O (n 2 ).

Но что именно O (log n) ? Например, что означает сказать, что высота полного двоичного дерева O (log n) ?

Я знаю (может быть, не очень подробно), что такое Логарифм, в том смысле, что: log 10 100 = 2, но я не могу понять, как определить функцию с логарифмическим временем.


1712


источник


Ответы:


Я не могу понять, как определить функцию с временем журнала.

Наиболее распространенными атрибутами логарифмической функции времени выполнения являются:

  • выбор следующего элемента, на котором можно выполнить какое-либо действие, является одной из нескольких возможностей, и
  • нужно выбрать только один.

или

  • элементы, на которых выполняется действие, являются цифрами n

Вот почему, например, поиск людей в телефонной книге - O (log n). Вам не нужно проверять каждый человек в телефонной книге, чтобы найти правильный; вместо этого вы можете просто делить и побеждать, глядя на то, где их имя в алфавитном порядке, и в каждом разделе вам нужно всего лишь изучить подмножество каждого раздела, прежде чем вы в конечном итоге найдете чей-то номер телефона.

Конечно, большая телефонная книга по-прежнему займет у вас больше времени, но она не будет расти так же быстро, как пропорциональное увеличение дополнительного размера.


Мы можем расширить пример телефонной книги, чтобы сравнить другие виды операций и их Продолжительность. Мы предположим, что наша телефонная книга имеет бизнес («Желтые страницы»), которые имеют уникальные имена и люди («Белые страницы»), которые могут не иметь уникальных имен. Номер телефона присваивается не более чем одному человеку или бизнесу. Мы также предположим, что для перехода на определенную страницу требуется постоянное время.

Вот время работы некоторых операций, которые мы могли бы выполнять в телефонной книге, от лучших до худших:

  • O (1) (наилучший вариант): На странице, на которой указано имя компании, и название компании, найдите номер телефона.

  • O (1) (средний случай): На странице, на которой указано имя человека, и его имя, найдите номер телефона.

  • O (log n): Учитывая имя человека, найдите номер телефона, выбрав случайную точку примерно на половину той части книги, которую вы еще не искали, а затем проверяете, находится ли имя человека в этой точке. Затем повторите процесс примерно наполовину через ту часть книги, где лежит имя человека. (Это двоичный поиск имени человека.)

  • На): Найдите всех людей, чьи номера телефонов содержат цифру «5».

  • На): Учитывая номер телефона, найдите человека или компанию с этим номером.

  • O (n log n): В офисе принтера была путаница, и в нашей телефонной книге были вставлены все его страницы в случайном порядке. Исправьте порядок, чтобы он был правильным, посмотрев первое имя на каждой странице, а затем разместив эту страницу в соответствующем месте в новой пустой телефонной книге.

Для приведенных ниже примеров мы сейчас находимся в офисе принтера. Телефонные книги ждут отправки по почте каждому резиденту или бизнесу, и на каждой телефонной книжке есть стикер, определяющий, куда он должен быть отправлен. Каждый человек или бизнес получает одну телефонную книгу.

  • O (n log n): Мы хотим персонализировать телефонную книгу, поэтому мы собираемся найти имя каждого человека или бизнеса в их обозначенной копии, затем нарисуем их имя в книге и напишем короткую благодарственную записку за их покровительство.

  • На 2 ): В офисе произошла ошибка, и каждая запись в каждой телефонной книжке имеет дополнительный «0» в конце номера телефона. Возьмите немного белого цвета и удалите каждый ноль.

  • O (n · n!): Мы готовы загрузить телефонные книги на док-станцию. К сожалению, робот, который должен был загружать книги, пошатнулся: он помещает книги в грузовик в случайном порядке! Хуже того, он загружает все книги в грузовик, а затем проверяет, находятся ли они в правильном порядке, а если нет, он выгружает их и начинается. (Это страшный bogo sort .)

  • На N ): Вы устанавливаете робота так, чтобы он правильно загружал вещи. На следующий день один из ваших сотрудников играет на вас шутку и прокладывает загрузку док-робота в автоматизированные системы печати. Каждый раз, когда робот загружает оригинальную книгу, фабричный принтер выполняет дублирование всех телефонных книг! К счастью, системы обнаружения ошибок робота достаточно сложны, что робот не пытается печатать еще больше копий, когда он сталкивается с дубликатой книгой для загрузки, но ей все равно приходится загружать каждую оригинальную и дублируемую книгу, которая была напечатана.


2145



Много хороших ответов уже было опубликовано на этот вопрос, но я считаю, что мы действительно пропускаем важный, а именно, иллюстрированный ответ.

Что значит сказать, что высота полного двоичного дерева равна O (log n)?

На следующем рисунке изображено двоичное дерево. Обратите внимание, как каждый уровень содержит удвоенное количество узлов по сравнению с уровнем выше (следовательно, двоичный ):

Binary tree

Бинарный поиск - пример со сложностью O(log n), Предположим, что узлы нижнего уровня дерева на рисунке 1 представляют элементы в некоторой сортированной коллекции. Двоичный поиск - это алгоритм разделения и покоя, и рисунок показывает, как нам понадобится (самое большее) 4 сравнения, чтобы найти запись, которую мы ищем в этом наборе данных 16 элементов.

Предположим, у нас вместо этого был набор данных с 32 элементами. Продолжайте рисовать выше, чтобы найти, что нам теперь понадобятся 5 сравнений, чтобы найти то, что мы ищем, поскольку дерево только выросло на один уровень глубже, когда мы умножали объем данных. В результате сложность алгоритма может быть описана как логарифмический порядок.

Заговор log(n)на обычном листе бумаги, приведет к графику, где рост кривой замедляется как nувеличивается:

O(log n)


506



O(log N)в основном означает, что время растет линейно, а nрастет экспоненциально. Так что если это потребуется 1второй для вычисления 10элементов, это займет 2секунд для вычисления 100элементы, 3секунд для вычисления 1000элементы и т. д.

Это O(log n)когда мы делим и управляем типом алгоритмов, например бинарный поиск. Другим примером является быстрая сортировка, где каждый раз мы делим массив на две части и каждый раз, когда это требуется O(N)чтобы найти элемент поворота. Следовательно, это N O(log N)


457



Приведенное ниже объяснение использует случай полного сбалансированный бинарное дерево, чтобы помочь вам понять, как мы получаем логарифмическую временную сложность.

Двоичное дерево - это случай, когда проблема размера n делится на подзадачу размером n / 2, пока мы не достигнем проблемы размера 1:

height of a binary tree

И именно так вы получаете O (log n), который представляет собой объем работы, который необходимо выполнить над указанным выше деревом для достижения решения.

Общим алгоритмом с временной сложностью O (log n) является двоичный поиск, рекурсивным отношением которого является T (n / 2) + O (1), то есть на каждом последующем уровне дерева вы делите проблему на половину и выполняете постоянную дополнительную работу.


194



If you had a function that takes:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Then it takes log2(n) time. The Big O notation, loosely speaking, means that the relationship only needs to be true for large n, and that constant factors and smaller terms can be ignored.


119



Overview

Others have given good diagram examples, such as the tree diagrams. I did not see any simple code examples. So in addition to my explanation, I'll provide some algorithms with simple print statements to illustrate the complexity of different algorithm categories.

First, you'll want to have a general idea of Logarithm, which you can get from https://en.wikipedia.org/wiki/Logarithm . Natural science use e and the natural log. Engineering disciples will use log_10 (log base 10) and computer scientists will use log_2 (log base 2) a lot, since computers are binary based. Sometimes you'll see abbreviations of natural log as ln(), engineers normally leave the _10 off and just use log() and log_2 is abbreviated as lg(). All of the types of logarithms grow in a similar fashion, that is why they share the same category of log(n).

When you look at the code examples below, I recommend looking at O(1), then O(n), then O(n^2). After you are good with those, then look at the others. I've included clean examples as well as variations to demonstrate how subtle changes can still result in the same categorization.

You can think of O(1), O(n), O(logn), etc as classes or categories of growth. Some categories will take more time to do than others. These categories help give us a way of ordering the algorithm performance. Some grown faster as the input n grows. The following table demonstrates said growth numerically. In the table below think of log(n) as the ceiling of log_2.

enter image description here

Simple Code Examples Of Various Big O Categories:

O(1) - Constant Time Examples:

  • Algorithm 1:

Algorithm 1 prints hello once and it doesn't depend on n, so it will always run in constant time, so it is O(1).

print "hello";
  • Algorithm 2:

Algorithm 2 prints hello 3 times, however it does not depend on an input size. Even as n grows, this algorithm will always only print hello 3 times. That being said 3, is a constant, so this algorithm is also O(1).

print "hello";
print "hello";
print "hello";

O(log(n)) - Logarithmic Examples:

  • Algorithm 3 - This acts like "log_2"

Algorithm 3 demonstrates an algorithm that runs in log_2(n). Notice the post operation of the for loop multiples the current value of i by 2, so i goes from 1 to 2 to 4 to 8 to 16 to 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algorithm 4 - This acts like "log_3"

Algorithm 4 demonstrates log_3. Notice i goes from 1 to 3 to 9 to 27...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algorithm 5 - This acts like "log_1.02"

Algorithm 5 is important, as it helps show that as long as the number is greater than 1 and the result is repeatedly multiplied against itself, that you are looking at a logarithmic algorithm.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O(n) - Linear Time Examples:

  • Algorithm 6

This algorithm is simple, which prints hello n times.

for(int i = 0; i < n; i++)
  print "hello";
  • Algorithm 7

This algorithm shows a variation, where it will print hello n/2 times. n/2 = 1/2 * n. We ignore the 1/2 constant and see that this algorithm is O(n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O(n*log(n)) - nlog(n) Examples:

  • Algorithm 8

Think of this as a combination of O(log(n)) and O(n). The nesting of the for loops help us obtain the O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algorithm 9

Algorithm 9 is like algorithm 8, but each of the loops has allowed variations, which still result in the final result being O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O(n^2) - n squared Examples:

  • Algorithm 10

O(n^2) is obtained easily by nesting standard for loops.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algorithm 11

Like algorithm 10, but with some variations.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O(n^3) - n cubed Examples:

  • Algorithm 12

This is like algorithm 10, but with 3 loops instead of 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algorithm 13

Like algorithm 12, but with some variations that still yield O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Summary

The above give several straight forward examples, and variations to help demonstrate what subtle changes can be introduced that really don't change the analysis. Hopefully it gives you enough insight.


101



Logarithmic running time (O(log n)) essentially means that the running time grows in proportion to the logarithm of the input size - as an example, if 10 items takes at most some amount of time x, and 100 items takes at most, say, 2x, and 10,000 items takes at most 4x, then it's looking like an O(log n) time complexity.


82



You can think of O(log N) intuitively by saying the time is proportional to the number of digits in N.

If an operation performs constant time work on each digit or bit of an input, the whole operation will take time proportional to the number of digits or bits in the input, not the magnitude of the input; thus, O(log N) rather than O(N).

If an operation makes a series of constant time decisions each of which halves (reduces by a factor of 3, 4, 5..) the size of the input to be considered, the whole will take time proportional to log base 2 (base 3, base 4, base 5...) of the size N of the input, rather than being O(N).

And so on.


54



The logarithm

Ok let's try and fully understand what a logarithm actually is.

Imagine we have a rope and we have tied it to a horse. If the rope is directly tied to the horse, the force the horse would need to pull away (say, from a man) is directly 1.

Now imagine the rope is looped round a pole. The horse to get away will now have to pull many times harder. The amount of times will depend on the roughness of the rope and the size of the pole, but let's assume it will multiply one's strength by 10 (when the rope makes a complete turn).

Now if the rope is looped once, the horse will need to pull 10 times harder. If the human decides to make it really difficult for the horse, he may loop the rope again round a pole, increasing it's strength by an additional 10 times. A third loop will again increase the strength by a further 10 times.

enter image description here

We can see that for each loop, the value increases by 10. The number of turns required to get any number is called the logarithm of the number i.e. we need 3 posts to multiple your strength by 1000 times, 6 posts to multiply your strength by 1,000,000.

3 is the logarithm of 1,000, and 6 is the logarithm of 1,000,000 (base 10).

So what does O(log n) actually mean?

In our example above, our 'growth rate' is O(log n). For every additional loop, the force our rope can handle is 10 times more:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Now the example above did use base 10, but fortunately the base of the log is insignificant when we talk about big o notation.

Now let's imagine you are trying to guess a number between 1-100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Now it took you 7 guesses to get this right. But what is the relationship here? What is the most amount of items that you can guess from each additional guess?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Using the graph, we can see that if we use a binary search to guess a number between 1-100 it will take us at most 7 attempts. If we had 128 numbers, we could also guess the number in 7 attemps but 129 numbers will takes us at most 8 attempts (in relations to logarithms, here we would need 7 guesses for a 128 value range, 10 guesses for a 1024 value range. 7 is he logarithm of 128, 10 is the logarithm of 1024 (base 2)).

Notice that I have bolded 'at most'. Big o notation always refers to the worse case. If you're lucky, you could guess the number in one attempt and so the best case is O(1), but that's another story.

We can see that for every guess our data set is shrinking. A good rule of thumb to identify if an algorithm has a logarithmtic time is to see if the data set shrinks by a certain order after each iteration

What about O(n log n)?

You will eventually come across a linerarithmic time O(n log(n) algorithm. The rule of thumb above applies again, but this time the logarithmic function has to run n times e.g. reducing the size of a list n times, which occurs in algorithms like a mergesort.

You can easily identify if the algorithmic time is n log n. Look for an outer loop which iterates through a list (O(n)). Then look to see if there is an inner loop. If the inner loop is cutting/reducing the data set on each iteration, that loop is (O(log n), and so the overall algorithm is = O(n log n).

Disclaimer: The rope-logarithm example was grabbed from the excellent Mathematician's Delight book by W.Sawyer.


53



The best way I've always had to mentally visualize an algorithm that runs in O(log n) is as follows:

If you increase the problem size by a multiplicative amount (i.e. multiply its size by 10), the work is only increased by an additive amount.

Applying this to your binary tree question so you have a good application: if you double the number of nodes in a binary tree, the height only increases by 1 (an additive amount). If you double it again, it still only increased by 1. (Obviously I'm assuming it stays balanced and such). That way, instead of doubling your work when the problem size is multiplied, you're only doing very slightly more work. That's why O(log n) algorithms are awesome.


47