Когда происходит обозначение BigOh O (log n)?

Question

Можете ли вы объяснить, что делает алгоритм O (log n)?

Буду признателен, если вы покажете его простым кодом.

Спасибо

Answer 1

log(n)/log(i) является решением для отношения возврата

f(n) =  f(n/i) + c

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

function(input, N){
   do some constant work
   return function(input, N/c);
}

Тогда у вас сложность Theta(logn).

Примеры:

• При поиске в сбалансированном дереве поиска: возьмите дереворазмером n, если он равен возврату корня (константе), или искать в левом поддереве, если меньше (размер n / 2), искать в правом поддереве (размер n / 2), если больше.
• Экспонента a^n: если n = 1, вернуть a.В противном случае возведите в степень a^(n/2) = b (проблема размера n / 2), умножьте b на b и, если n чётно, умножьте на один раз.

Answer 2

Википедия дает несколько примеров порядков общих функций:

O (log (n)), Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированногодерево поиска, а также все операции в биноминальной куче.

Answer 3

См. Простое английское объяснение Большого О . Там объяснено.

Самое простое определение, которое я могу дать для обозначения Big-O, это:

Обозначение Big-O является относительным представлением сложности алгоритма.

В этом есть несколько важных и намеренно выбранных слов предложение:

• относительно: Вы можете сравнивать только яблоки с яблоками. Вы не можете сравнить алгоритм для выполнения арифметического умножения с алгоритмом это сортирует список целых чисел. Но два алгоритма, которые делают арифметику операции (одно умножение, одно сложение) скажут вам кое-что смысл;
• представление: Big-O (в простейшем виде) сокращает сравнение между алгоритмами до одной переменной. Эта переменная выбирается на основании наблюдений или предположений. Например, сортировка алгоритмы обычно сравниваются на основе операций сравнения (сравнение двух узлов для определения их относительного порядка). это предполагает, что сравнение стоит дорого. Но что, если сравнение дешево но обмен дорогой? Это меняет сравнение; и
• сложность: если мне понадобится одна секунда, чтобы отсортировать 10 000 элементов, сколько времени мне понадобится, чтобы отсортировать миллион? Сложность в этом экземпляр является относительной мерой к чему-то другому.

Вернитесь и перечитайте вышесказанное, когда прочтете остальные.

Лучший пример Биг-О, о котором я могу думать, - это арифметика. принимать два числа (123456 и 789012). Основные арифметические операции мы в школе учились:

• вычитание;
• умножение; и
• разделение.

Каждый из них является операцией или проблемой. Метод решения этих называется алгоритм .

Дополнение самое простое. Вы выравниваете числа вверх (вправо) и добавить цифры в столбце, записывающие последний номер этого дополнения в результат. «Десятки» часть этого числа переносится на следующий столбец.

Давайте предположим, что добавление этих чисел является самым дорогим операция в этом алгоритме. Разумеется, чтобы добавить эти два числа вместе мы должны сложить вместе 6 цифр (и, возможно, нести 7-й). Если мы добавим два 100-значных числа вместе, мы должны сделать 100 дополнений. Если мы добавим два числа из 10000 цифр, мы должны сделать 10 000 дополнений.

Видите образец? сложность (количество операций) прямо пропорционально количеству цифр n в большем число. Мы называем это O (n) или линейная сложность .

Вычитание аналогично (за исключением того, что вам может понадобиться брать взаймы вместо нести).

Умножение отличается. Вы выстраиваете числа, берете первое цифра в нижнем числе и умножьте ее по очереди на каждую цифру в верхнем числе и так далее через каждую цифру. Таким образом, чтобы умножить наш два 6-значных чисел мы должны сделать 36 умножений. Возможно, нам нужно сделать добавляется целых 10 или 11 столбцов, чтобы получить конечный результат.

Если у нас есть два 100-значных числа, нам нужно сделать 10 000 умножений и 200 добавляет. Для двух миллионов цифр нам нужно сделать одно триллион (10 ¹² ) умножений и два миллиона добавлений.

Поскольку алгоритм масштабируется с n- в квадрате , это O (n ² ) или квадратичная сложность . Это хорошее время, чтобы представить другой Важная концепция:

Мы заботимся только о самой значительной части сложности.

Проницательный, возможно, понял, что мы могли бы выразить число операции как: n ² + 2n. Но, как вы видели из нашего примера с двумя числами по миллиону цифр в каждом втором члене (2n)становится незначительным (что составляет 0,00002% от общего объема операций на этом этапе).

Телефонная книга

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

Теперь, если вы указали компьютеру найти номер телефона для «Джон Смит», что бы вы сделали? Игнорируя тот факт, что вы могли угадайте, как далеко в S началось (предположим, вы не можете), что бы Вы делаете?

Типичной реализацией может быть открытие до середины, возьмите 500 000 ^th и сравните это с "Смитом". Если это случится «Смит, Джон», нам просто повезло. Гораздо более вероятно, что "Джон Смит "будет до или после этого имени. Если это после того, как мы разделите последнюю половину телефонной книги пополам и повторите. Если это до этого мы делим первую половину телефонной книги пополам и повторение. И так далее.

Это называется поиском пополам и используется каждый день в программирование, понимаете ли вы это или нет.

Итак, если вы хотите найти имя в телефонной книге с миллионами имен, вы на самом деле можно найти любое имя, делая это не более 21 раза (я может быть выключен на 1). Сравнивая алгоритмы поиска, мы решаем, что это сравнение - наше 'n'.

Для телефонной книги из 3 имен требуется 2 сравнения (самое большее).
Для 7 - максимум 3.
Для 15 - 4.
...
Для 1 000 000 требуется 21 или около того.

Это потрясающе хорошо, не правда ли?

В терминах Big-O это O (log n) или логарифмическая сложность . Теперь рассматриваемый логарифм может быть ln (основание e), log ₁₀ , log ₂ или какая-то другая база. Неважно, что это все еще O (log n) точно так же, как O (2n ² ) и O (100n ² ) все еще оба O (n ² ).

Answer 4

Самый простой пример: бинарный поиск

Принцип : на каждом шаге убирается половина возможного пространства поиска (искомый массив), самое большее после логаn) шаги, которые должен завершить алгоритм (из-за разрезания пополам).