Что именно означает O(log n)

time-complexity big-o


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

Например, следующая функция - O (n), потому что алгоритм растет пропорционально его входу 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, но я не могу понять, как идентифицировать функцию с логарифмическим временем.




Answer 1 John Feminella


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

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

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

or

  • элементы,на которых выполняется действие,представляют собой цифры 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 2 ): в офисе произошла ошибка, и каждая запись в каждой телефонной книге имеет дополнительный «0» в конце номера телефона. Возьмите немного белого и уберите каждый ноль.

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

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




Answer 2 fastcodejava


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

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




Answer 3 Jørn Schou-Rode


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

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

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

Binary tree

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

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

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

O(log n)




Answer 4 2cupsOfTech


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

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

height of a binary tree

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

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




Answer 5 James Oravec


Overview

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

Во-первых, вы хотите получить общее представление о логарифме, которое вы можете получить по адресу https://en.wikipedia.org/wiki/Logarithm . Естествознание использует e и натуральное бревно. Ученики-инженеры будут использовать log_10 (база 10 журналов), а ученые-программисты будут часто использовать log_2 (база 2 журналов), поскольку компьютеры работают на двоичном языке. Иногда вы видите сокращения натурального журнала как ln() , инженеры обычно оставляют _10 выключенным и просто используют log() а log_2 сокращается как lg() . Все типы логарифмов растут одинаковым образом, поэтому они разделяют одну и ту же категорию log(n) .

Когда вы смотрите на примеры кода ниже,я рекомендую посмотреть на O(1),затем O(n),затем O(n^2).После того,как вы хорошо справитесь с ними,посмотрите на другие.Я включил как чистые примеры,так и вариации,чтобы продемонстрировать,как едва уловимые изменения могут привести к той же категории.

Вы можете думать об O(1),O(n),O(logn)и т.д.как о классах или категориях роста.Некоторые категории займут больше времени,чем другие.Эти категории помогают нам упорядочить работу алгоритма.Некоторые из них растут быстрее по мере роста входных n.В следующей таблице показан указанный рост в числовом выражении.В следующей таблице подумайте о log(n)как о потолке log_2.

enter image description here

Примеры простых кодов различных категорий Big O:

O (1) - Примеры с постоянным временем:

  • Алгоритм 1:

Алгоритм 1 выводит hello один раз, и он не зависит от n, поэтому он всегда будет работать в постоянное время, поэтому это O(1) .

print "hello";
  • Алгоритм 2:

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

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

O (log (n)) - Логарифмические примеры:

  • Алгоритм 3 - действует как «log_2»

Алгоритм 3 демонстрирует алгоритм, который работает в log_2 (n). Обратите внимание, что операция post цикла for умножает текущее значение i на 2, поэтому значение i увеличивается от 1 до 2, от 4 до 8, от 16 до 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Алгоритм 4 - действует как «log_3»

Алгоритм 4 демонстрирует log_3. Обратите внимание, i иду от 1 до 3 до 9 до 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Алгоритм 5 - действует как «log_1.02»

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

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

O (n) - Примеры линейного времени:

  • Алгоритм 6

Этот алгоритм прост,который печатает привет n раз.

for(int i = 0; i < n; i++)
  print "hello";
  • Алгоритм 7

Этот алгоритм показывает вариацию,где он будет печатать приветствие n/2 раза.n/2=1/2*n.Мы игнорируем константу 1/2 и видим,что этот алгоритм является O(n).

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

O (n * log (n)) - nlog (n) Примеры:

  • Алгоритм 8

Думайте об этом как о комбинации O(log(n)) и O(n) . Вложенность циклов for помогает нам получить O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Алгоритм 9

Алгоритм 9 аналогичен алгоритму 8, но каждый из циклов допускает изменения, которые все же приводят к конечному результату 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 в квадрате Примеры:

  • Алгоритм 10

O(n^2) легко получается путем вложения стандарта для циклов.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Алгоритм 11

Как алгоритм 10,но с некоторыми вариациями.

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

O (n ^ 3) - n куб. Примеры:

  • Алгоритм 12

Это похоже на алгоритм 10,но с 3 циклами вместо 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Алгоритм 13

Как и алгоритм 12, но с некоторыми вариациями, которые все еще дают 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

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