Big-O для восьмилетних?[дубликат]

StackOverflow https://stackoverflow.com/questions/107165

Вопрос

На этот вопрос уже есть ответ здесь:

Я спрашиваю больше о том, что это значит для моего кода.Я понимаю эти концепции математически, мне просто трудно уяснить, что они означают концептуально.Например, если нужно выполнить операцию O(1) над структурой данных, я понимаю, что количество операций, которые она должна выполнить, не увеличится, потому что элементов станет больше.А операция O(n) будет означать, что вы должны выполнить набор операций над каждым элементом.Может ли кто-нибудь заполнить здесь пробелы?

  • Например, что именно будет делать операция O(n^2)?
  • И что, черт возьми, это значит, если операция равна O(n log(n))?
  • И нужно ли кому-то курить крэк, чтобы написать O(x!)?
Это было полезно?

Решение

Один из способов думать об этом таков:

O(N^2) означает, что для каждого элемента вы что-то делаете с каждым другим элементом, например сравниваете их.Пузырьковая сортировка является примером этого.

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

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

Другие советы

Самое важное, что нотация Big-O означает для вашего кода, это то, как он будет масштабироваться, когда вы удвоите количество «вещей», с которыми он работает.Вот конкретный пример:

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

Итак, возьмите быструю сортировку, которая равна O(n log(n)) и пузырьковую сортировку, которая равна O(n^2).При сортировке 10 объектов быстрая сортировка работает в 3 раза быстрее, чем пузырьковая сортировка.А вот при сортировке 100 вещей — в 14 раз быстрее!Очевидно, что тогда важно выбрать самый быстрый алгоритм.Когда вы доберетесь до баз данных с миллионом строк, это может означать разницу между выполнением вашего запроса за 0,2 секунды и часами.

Еще одна вещь, которую следует учитывать, это то, что закон Мура не может помочь плохому алгоритму.Например, если у вас есть какой-то научный расчет O(n^3) и он может вычислить 100 операций в день, удвоение скорости процессора даст вам только 125 операций в день.Однако уменьшите это вычисление до O(n^2), и вы будете делать 1000 дел в день.

уточнение:На самом деле Big-O ничего не говорит о сравнительной производительности разных алгоритмов в одной и той же конкретной точке размера, а скорее о сравнительной производительности одного и того же алгоритма в разных точках размера:

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

Возможно, вам будет полезно визуализировать это:

Big O Analysis

Кроме того, на ЛогY/LogX масштабировать функции н1/2, н, н2 все похоже прямые линии, пока включен ЛогY/X шкала 2н, ен, 10н представляют собой прямые линии и н! является линеарифмическим (выглядит как н войти н).

Это может быть слишком математическим подходом, но вот моя попытка.(Я являюсь математик.)

Если что-то О(ж(н)), то время работы на н элементы будут равны А ж(н) + Б (измеряется, скажем, в тактовых циклах или операциях ЦП).Ключ к пониманию того, что у вас тоже есть эти константы А и Б, которые возникают в результате конкретной реализации. Б по сути представляет собой «постоянные накладные расходы» вашей операции, например, некоторую предварительную обработку, которую вы выполняете, которая не зависит от размера коллекции. А представляет скорость вашего фактического алгоритма обработки элементов.

Ключевым моментом, однако, является то, что вы используете большую букву О, чтобы выяснить насколько хорошо что-то будет масштабироваться.Так что эти константы не будут иметь особого значения:если вы пытаетесь понять, как масштабировать количество элементов от 10 до 10 000, кого волнуют постоянные накладные расходы? Б?Точно так же другие проблемы (см. ниже), безусловно, перевесят вес мультипликативной константы. А.

Так что реальная сделка ж(н).Если ж растет совсем не с н, например ж(н) = 1, тогда вы будете фантастически масштабироваться --- ваше время работы всегда будет А + Б.Если ж растет линейно с н, т.е. ж(н) = н, ваше время выполнения будет масштабироваться настолько хорошо, насколько можно ожидать - если ваши пользователи ждут 10 нс для 10 элементов, они будут ждать 10 000 нс для 10 000 элементов (игнорируя аддитивную константу).Но если он растет быстрее, например н2, тогда у тебя проблемы;дела начнут слишком сильно замедляться, когда вы соберете большие коллекции. ж(н) = н бревно(н) является хорошим компромиссом, обычно:ваша операция не может быть настолько простой, чтобы обеспечить линейное масштабирование, но вам удалось сократить ее так, что она будет масштабироваться намного лучше, чем ж(н) = н2.

Практически вот несколько хороших примеров:

  • О(1):получение элемента из массива.Мы точно знаем, где он находится в памяти, поэтому просто идем и получаем его.Не имеет значения, содержит ли коллекция 10 или 10 000 элементов;он все еще находится под индексом (скажем) 3, поэтому мы просто переходим к ячейке 3 в памяти.
  • О(н):получение элемента из связанного списка.Здесь, А = 0,5, потому что в среднем вам придется просмотреть половину связанного списка, прежде чем вы найдете искомый элемент.
  • О(н2):различные «тупые» алгоритмы сортировки.Потому что, как правило, их стратегия предполагает для каждого элемента (н), вы смотрите на все остальные элементы (так раз другой н, давая н2), то расположитесь в нужном месте.
  • О(н бревно(н)):различные «умные» алгоритмы сортировки.Оказывается, вам нужно просмотреть, скажем, только 10 элементов из 10.10-коллекция элементов для разумной сортировки по отношению к каждый еще в коллекции.Потому что все остальные также Я собираюсь рассмотреть 10 элементов, и возникающее поведение организовано так, что этого достаточно для создания отсортированного списка.
  • О(н!):алгоритм, который «пробует все», поскольку существует (пропорционально) н!возможные комбинации н элементы, которые могут решить данную проблему.Поэтому он просто перебирает все такие комбинации, пробует их, а затем останавливается, когда это удается.

Ответ don.neufeld очень хорош, но я бы, вероятно, объяснил его двумя частями:во-первых, существует грубая иерархия O(), в которую попадает большинство алгоритмов.Затем вы можете просмотреть каждый из них и придумать эскизы того, что типичный алгоритмы той временной сложности делают.

Для практических целей единственные O(), которые когда-либо имели значение:

  • O(1) «постоянное время» — требуемое время не зависит от размера входных данных.В качестве грубой категории я бы включил сюда такие алгоритмы, как поиск по хешу и Union-Find, хотя ни один из них на самом деле не является O(1).
  • O(log(n)) «логарифмический» — он становится медленнее по мере увеличения входных данных, но как только ваши входные данные станут достаточно большими, они не изменятся настолько, чтобы о них можно было беспокоиться.Если ваша среда выполнения подходит для данных разумного размера, вы можете заполнить ее любым количеством дополнительных данных, и все равно все будет в порядке.
  • O(n) «линейный» — чем больше входных данных, тем больше времени это занимает при равном компромиссе.В три раза больший размер ввода займет примерно в три раза больше времени.
  • O(n log(n)) «лучше, чем квадратичное» — увеличение размера входных данных вредно, но с этим все же можно справиться.Алгоритм, наверное, достойный, просто основная проблема сложнее (решения менее локализованы относительно входных данных), чем те задачи, которые можно решить за линейное время.Если ваши входные размеры растут, не думайте, что вы обязательно сможете обрабатывать вдвое больший размер, не меняя архитектуру (например, перейдя на ночные пакетные вычисления или не выполняя действия по кадрам).Однако ничего страшного, если размер ввода немного увеличится;просто следите за кратностью.
  • O(n^2) «квадратичное» — на самом деле оно будет работать только до определенного размера вашего ввода, поэтому обратите внимание на то, насколько большим он может стать.Кроме того, ваш алгоритм может оказаться отстойным — хорошенько подумайте, существует ли алгоритм O(n log(n)) который даст вам то, что вам нужно.Оказавшись здесь, почувствуйте огромную благодарность за великолепное оборудование, которое нам подарили.Еще совсем недавно то, что вы пытаетесь сделать, было бы невозможно с практической точки зрения.
  • O(n^3) "кубический" - качественно не сильно отличается от O(n^2).Те же комментарии применимы, только в большей степени.Есть большая вероятность, что более умный алгоритм сможет на этот раз сократить время до чего-то меньшего, например, O(n^2 log(n)) или O(n^2,8...), но опять же, есть хороший шанс, что это не будет стоить хлопот.(Вы уже ограничены в практическом размере входных данных, поэтому постоянные коэффициенты, которые могут потребоваться для более умных алгоритмов, вероятно, перечеркнут их преимущества для практических случаев.Кроме того, мышление замедлено;Если вы позволите компьютеру разобраться в этом, вы в целом сэкономите время.)
  • O(2^n) «экспоненциальный» — проблема либо принципиально сложна в вычислительном отношении, либо вы идиот.Эти проблемы имеют узнаваемый оттенок.Размеры входных данных ограничены довольно конкретным жестким пределом.Вы быстро узнаете, вписываетесь ли вы в этот предел.

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

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

  • O(1) — вы просматриваете только часть входных данных фиксированного размера, а, возможно, и ничего из этого.Пример:максимум отсортированного списка.
    • Или ваш размер ввода ограничен.Пример:сложение двух чисел.(Обратите внимание, что сложение N чисел происходит за линейное время.)
  • O(log n) — каждый элемент вашего ввода сообщает вам достаточно, чтобы игнорировать большую часть остальной части ввода.Пример:когда вы смотрите на элемент массива в двоичном поиске, его значение говорит вам, что вы можете игнорировать «половину» вашего массива, не просматривая ни одной его части.Или, аналогичным образом, элемент, на который вы смотрите, дает вам достаточно информации о части оставшихся входных данных, и вам не нужно будет на него смотреть.
    • Однако в половинках нет ничего особенного — если вы можете игнорировать только 10% вашего ввода на каждом шаге, это все равно будет логарифмическим.
  • O(n) — вы выполняете фиксированный объем работы для каждого входного элемента.(Но см. ниже.)
  • O(n log(n)) - есть несколько вариантов.
    • Вы можете разделить входные данные на две стопки (не более чем за линейное время), решить задачу независимо для каждой стопки, а затем объединить две стопки, чтобы сформировать окончательное решение.Независимость двух свай имеет ключевое значение.Пример:классическая рекурсивная сортировка слиянием.
    • Каждый проход по данным за линейное время приближает вас к полпути к решению.Пример:быстрая сортировка, если вы думаете о максимальном расстоянии каждого элемента до его окончательной отсортированной позиции на каждом этапе разделения (и да, я знаю, что на самом деле это O (n ^ 2) из-за вырожденного выбора опорной точки.Но на практике это попадает в мою категорию O(n log(n))).
  • O(n^2) — вам нужно просмотреть каждую пару входных элементов.
    • Или нет, но вы думаете, что да, и используете неправильный алгоритм.
  • О(n^3) - эм...У меня нет четкой характеристики этих вещей.Вероятно, это одно из:
    • Вы умножаете матрицы
    • Вы просматриваете каждую пару входных данных, но выполняемая вами операция требует повторного просмотра всех входных данных.
    • вся графовая структура вашего ввода актуальна
  • O(2^n) — вам нужно учитывать все возможные подмножества ваших входных данных.

Ни один из них не является строгим.Особенно не алгоритмы с линейным временем (O(n)):Я мог бы привести ряд примеров, в которых вам нужно просмотреть все входные данные, затем половину из них, затем половину из них и т. д.Или наоборот — вы складываете пары входных данных, а затем рекурсивно обрабатываете выходные данные.Они не соответствуют приведенному выше описанию, поскольку вы не просматриваете каждый входной сигнал один раз, но он все равно поступает в линейном времени.Тем не менее, в 99,2% случаев линейное время означает просмотр каждого входного сигнала один раз.

Многие из них легко продемонстрировать с помощью чего-то не связанного с программированием, например, перетасовки карт.

Сортировка колоды карт путем просмотра всей колоды в поисках туза пик, затем просмотра всей колоды в поисках двойки пик и т. д. будет худшим случаем n^2, если колода уже отсортирована в обратном порядке.Вы просмотрели все 52 карты 52 раза.

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

Хорошо, здесь есть несколько очень хороших ответов, но почти все они, похоже, совершают одну и ту же ошибку, и она широко распространена.

Неформально мы пишем, что f(n) = O(g(n)), если с точностью до масштабного коэффициента и для всех n, больших некоторого n0, g(n) равно больше чем f(n).То есть f(n) растет не быстрее чем или есть ограниченный сверху по, g(n).Это ничего не говорит нам о том, как быстро растет f(n), за исключением того факта, что оно гарантированно не будет хуже, чем g(n).

Конкретный пример:п = О(2^п).Мы все знаем, что n растет гораздо медленнее, чем 2^n, и это дает нам право сказать, что оно ограничено экспоненциальной функцией.Между n и 2^n много места, так что это не очень тугой связана, но это все еще законная связь.

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

Если вместо этого мы хотим сказать, что функция растет точно так же быстро, как и какая-то другая функция, мы используем тэта чтобы подчеркнуть это (я напишу T(f(n)) для обозначения heta of f(n) в уценке).T( g(n) ) — это сокращение для ограничения из над и под на g(n), опять же, с точностью до масштабного коэффициента и асимптотически.

То есть f(n) = T(g(n)) <=> f(n) = O(g(n)) и g(n) = O(f(n)).В нашем примере мы видим, что n != T( 2^n ), потому что 2^n != O(n).

Зачем беспокоиться об этом?Потому что в своем вопросе вы пишете: «Кто -то должен курить трещины, чтобы написать O (x!)?» Ответ - нет - потому что в основном все, что вы пишете, будет ограничено сверху фактической функцией.Время выполнения быстрой сортировки равно O(n!) — это не жесткое ограничение.

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

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

Как это связано с вашим вопросом о практической реализации этих границ?К сожалению, нотация O( ) скрывает константы, с которыми приходится иметь дело в реальных реализациях.Итак, хотя мы и можем сказать, что, например, для операции T(n^2) нам нужно посетить каждую возможную пару элементов, мы не знаем, сколько раз нам нужно их посетить (за исключением того, что это не является функцией н).Таким образом, нам может потребоваться посетить каждую пару 10 раз или 10^10 раз, и оператор T(n^2) не делает различий.Функции низшего порядка также скрыты — нам может потребоваться посетить каждую пару элементов один раз, а каждый отдельный элемент — 100 раз, потому что n^2 + 100n = T(n^2).Идея нотации O( ) заключается в том, что для достаточно большого n это вообще не имеет значения, поскольку n^2 становится настолько большим, чем 100n, что мы даже не замечаем влияния 100n на время работы.Однако мы часто имеем дело с «достаточно малым» n, так что постоянные факторы и т. д. имеют реальное, существенное значение.

Например, быстрая сортировка (средняя стоимость T(n.log n)) и пирамидальная сортировка (средняя стоимость T(n.log n)) — это алгоритмы сортировки с одинаковой средней стоимостью, однако быстрая сортировка обычно намного быстрее пирамидальной сортировки.Это связано с тем, что пирамидальная сортировка выполняет несколько больше сравнений для каждого элемента, чем быстрая сортировка.

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

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

Я пытаюсь объяснить это на простых примерах кода на C#.

Для List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};

O(1) выглядит как

return numbers.First();

O(n) выглядит как

int result = 0;
foreach (int num in numbers)
{
    result += num;
}
return result;

O(n log(n)) выглядит так

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.length - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

O(n^2) выглядит так 

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

Похоже, О(н!) устал придумывать что-нибудь простое.
Но я надеюсь, вы поняли общую суть?

Я описываю это своим друзьям, не разбирающимся в технических вопросах, так:

Рассмотрим сложение многозначных чисел.Старое доброе дополнение с карандашом и бумагой.Тот, который вы узнали, когда вам было 7-8 лет.Имея два трех- или четырехзначных числа, вы можете довольно легко узнать, что они образуют в сумме.

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

Теперь рассмотрим многозначное умножение.Вы, вероятно, узнали об этом где-то в 8 или 9 лет.Вы (надеюсь) проделали множество повторяющихся упражнений, чтобы изучить механику, лежащую в основе этого.

Теперь представьте, что я дал вам те же самые два 100-значных числа и попросил умножить их.Это было бы много, много более сложная задача, на выполнение которой у вас уйдут часы — и вы вряд ли справитесь без ошибок.Причина этого в том, что (эта версия) умножения равна O(n^2);каждую цифру нижнего числа необходимо умножить на каждую цифру верхнего числа, в результате чего остается около n^2 операций.В случае 100-значных чисел это 10 000 умножений.

Нет, алгоритм O(n) не означает, что он будет выполнять операцию над каждым элементом.Обозначение Big-O дает вам возможность говорить о «скорости» вашего алгоритма независимо от вашей реальной машины.

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

Я думаю об этом так: перед вами стоит задача устранить проблему, вызванную каким-то злым злодеем В, который выбирает N, и вам нужно прикинуть, сколько времени потребуется, чтобы решить вашу проблему, когда он увеличит N.

O(1) -> увеличение N вообще не имеет никакого значения

O(log(N)) -> каждый раз, когда V удваивает N, вам приходится тратить дополнительное время T для выполнения задачи.V снова удваивает N, и вы тратите ту же сумму.

O(N) -> каждый раз, когда V удваивает N, вы тратите вдвое больше времени.

O(N^2) -> каждый раз, когда V удваивает N, вы тратите в 4 раза больше времени.(это нечестно!!!)

O(N log(N)) -> каждый раз, когда V удваивает N, вы тратите в два раза больше времени плюс немного больше.

Это границы алгоритма;Ученые-компьютерщики хотят описать, сколько времени потребуется для больших значений N.(это становится важным, когда вы факторизуете числа, используемые в криптографии: если компьютеры ускорятся в 10 раз, сколько еще бит вам придется использовать, чтобы гарантировать, что им все равно потребуется 100 лет, чтобы взломать ваше шифрование и не только 1 год?)

Некоторые границы могут иметь странное выражение, если это имеет значение для участвующих людей.Я видел такие вещи, как O(N log(N) log(log(N))) где-то в «Искусстве компьютерного программирования» Кнута для некоторых алгоритмов.(не помню, какой из них пришел мне в голову)

Еще один момент, который почему-то не был затронут:

Когда вы видите алгоритмы с такими вещами, как O(2^n) или O(n^3) или другими неприятными значениями, это часто означает, что вам придется принять несовершенный ответ на вашу проблему, чтобы получить приемлемую производительность.

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

Рассмотрим шахматы:Я не знаю точно, какое решение считается правильным, но, вероятно, это что-то вроде O(n^50) или даже хуже.Теоретически невозможно, чтобы какой-либо компьютер действительно вычислил правильный ответ — даже если вы используете каждую частицу во Вселенной в качестве вычислительного элемента, выполняющего операцию за минимально возможное время за время существования Вселенной, у вас все равно останется много нулей. .(Другой вопрос, сможет ли квантовый компьютер решить эту проблему.)

«Интуиция» позади Big-O

Представьте себе «конкуренцию» между двумя функциями по x, когда x приближается к бесконечности:f(x) и g(x).

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

Так, например, если для каждого x > 100 вы видите, что f(x) > g(x), то f(x) «быстрее», чем g(x).

В этом случае мы бы сказали g(x) = O(f(x)).f(x) представляет собой своего рода «ограничение скорости» для g(x), поскольку в конечном итоге она его преодолевает и навсегда оставляет позади.

Это не совсем определение обозначение «большое О», который также утверждает, что f(x) должно быть больше, чем C*g(x) только для некоторой константы C (это просто еще один способ сказать, что вы не можете помочь g(x) выиграть соревнование, умножив его на постоянный коэффициент - f(x) в конечном итоге всегда выиграет).В формальном определении также используются абсолютные значения.Но я надеюсь, что мне удалось сделать это интуитивно понятным.

  • И нужно ли кому-то курить крэк, чтобы написать O(x!)?

Нет, просто используйте Пролог.Если вы напишете алгоритм сортировки на Прологе, просто описав, что каждый элемент должен быть больше предыдущего, и позволите возврату выполнить сортировку за вас, это будет O(x!).Также известна как «сортировка перестановками».

Мне нравится ответ Дона Ньюфельда, но я думаю, что могу добавить кое-что об O(n log n).

Алгоритм, использующий простую стратегию «разделяй и властвуй», вероятно, будет O(log n).Самый простой пример — поиск чего-либо в отсортированном списке.Вы не начинаете с самого начала и не ищете его.Вы идете в середину, решаете, следует ли вам идти вперед или назад, прыгаете на полпути к последнему месту, которое вы смотрели, и повторяете это, пока не найдете искомый предмет.

Если вы посмотрите на алгоритмы быстрой сортировки или сортировки слиянием, вы увидите, что они оба используют подход, заключающийся в разделении списка, подлежащего сортировке, пополам, сортировке каждой половины (с использованием одного и того же алгоритма, рекурсивно), а затем повторном объединении двух половин.Этот вид рекурсивный Стратегия «разделяй и властвуй» будет равна O(n log n).

Если вы подумаете об этом внимательно, вы увидите, что быстрая сортировка выполняет алгоритм разделения O(n) для всех n элементов, затем разбиение O(n) дважды для n/2 элементов, затем 4 раза для n/4 элементов, и т. д...пока не дойдете до n разделов по 1 элементу (что является вырожденным).Число раз, которое вы делите n пополам, чтобы получить 1, примерно равно log n, и каждый шаг равен O (n), поэтому рекурсивное «разделяй и властвуй» составляет O (n log n).Сортировка слиянием строится по-другому, начиная с n рекомбинаций 1 элемента и заканчивая 1 рекомбинацией n элементов, где рекомбинация двух отсортированных списков равна O(n).

Что касается курения крэка для написания алгоритма O(n!), то это так, если только у вас нет выбора.Одной из таких задач считается приведенная выше задача коммивояжера.

Большинство книг Джона Бентли (например. Жемчуг программирования) освещают такие вещи очень прагматично. Этот разговор данное им включает один такой анализ быстрой сортировки.

Хотя это и не совсем относится к данному вопросу, Кнут придумал интересная идея:преподавать нотацию Big-O на уроках математического анализа в старших классах, хотя я нахожу эту идею довольно эксцентричной.

Думайте об этом как о складывании блоков LEGO (n) вертикально и перепрыгивании через них.

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

O(n) означает, что на каждом этапе вы складываете c блоков, где c1 — константа.

O(n^2) означает, что на каждом этапе вы складываете блоки c2 x n, где c2 — константа, а n — количество сложенных блоков.

O(nlogn) означает, что на каждом этапе вы складываете блоки c3 x n x log n, где c3 — константа, а n — количество сложенных блоков.

Чтобы понять O(n log n), помните, что log n означает log-base-2 от n.Затем посмотрите на каждую часть:

O(n) более или менее, когда вы работаете с каждым элементом в наборе.

O(log n) — это когда количество операций совпадает с показателем степени, до которого вы поднимаете 2, чтобы получить количество элементов.Например, двоичный поиск должен сократить множество пополам log n раз.

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

Просто отвечу на пару комментариев к моему сообщению выше:

Доменик - Я на этом сайте, и мне не все равно.Не из-за педантичности, а потому, что мы, программисты, обычно заботимся о точности.Неправильное использование нотации O( ) в стиле, который некоторые сделали здесь, делает ее бессмысленной;с таким же успехом мы можем сказать, что что-то занимает n^2 единиц времени как O(n^2) в соответствии с используемыми здесь соглашениями.Использование O( ) ничего не добавляет.Я говорю не просто о небольшом несоответствии между общепринятым употреблением и математической точностью, а о разнице между тем, имеет ли это смысл, а что нет.

Я знаю многих, многих отличных программистов, которые точно используют эти термины.Сказать: «О, мы программисты, поэтому нам все равно» удешевляет все предприятие.

по одному - Ну, не совсем, хотя я понимаю вашу точку зрения.Это не O(1) для сколь угодно большого n, что является своего рода определением O(·).Это просто показывает, что O( ) имеет ограниченную применимость для ограниченного n, когда мы предпочитаем говорить о количестве предпринятых шагов, а не об ограничении этого числа.

Скажите, что ваш журнал восьмилетней давности (n) означает, сколько раз вам придется разрезать бревно длиной n пополам, чтобы оно уменьшилось до размера n = 1 :p

O (n log n) обычно сортируется O (n^2), как правило, сравнивает все пары элементов

Предположим, у вас есть компьютер, который может решить задачу определенного размера.А теперь представьте, что мы можем удвоить производительность в несколько раз.Насколько большую проблему мы сможем решить с каждым удвоением?

Если мы сможем решить задачу удвоенного размера, это O(n).

Если у нас есть какой-то множитель, отличный от единицы, это своего рода полиномиальная сложность.Например, если каждое удвоение позволяет нам увеличить размер задачи примерно на 40 %, это будет O(n^2), а около 30% — это O(n^3).

Если мы просто увеличим размер проблемы, он станет экспоненциальным или даже хуже.Например, если каждое удвоение означает, что мы можем решить задачу на 1 большую, это O(2^n).(Вот почему перебор ключа шифрования становится практически невозможным с ключами разумного размера:128-битный ключ требует примерно в 16 квинтиллионов раз больше обработки, чем 64-битный.)

Помните басню о черепахе и зайце (черепахе и кролике)?

В долгосрочной перспективе побеждает черепаха, но в краткосрочной – заяц.

Это похоже на O(logN) (черепаха) против.О(Н) (заяц).

Если два метода различаются по своему большому О, то существует уровень N, на котором один из них выиграет, но большое О ничего не говорит о том, насколько велико это N.

Чтобы оставаться искренним в заданном вопросе, я бы ответил на него так же, как ответил бы 8-летнему ребенку.

Предположим, продавец мороженого готовит несколько порций мороженого (скажем, N) разной формы, расположенных в определенном порядке.Вы хотите съесть мороженое, лежащее посередине

Дело 1 :- Вы можете съесть мороженое, только если съели все мороженое меньше, чем оно, вам придется съесть половину всех подготовленных мороженого (вход). Ответ напрямую зависит от размера входного раствора будет (N)

Случай 2: — Вы можете съесть мороженое прямо посередине.

Решение будет O (1)

Случай 3:Вы можете съесть мороженое, только если вы съели все мороженое меньше, чем его, и каждый раз, когда вы едите мороженое, вы позволяете другому ребенку (новый ребенок каждый раз) есть все его мороженое, общее время было бы n + n + N ....... (N/2) Решение времена будет O (N2)

log(n) означает логарифмический рост.Примером могут служить алгоритмы «разделяй и властвуй».Если у вас есть 1000 отсортированных чисел в массиве (например.3, 10, 34, 244, 1203...) и хотите найти число в списке (найти его позицию), вы можете начать с проверки значения числа по индексу 500.Если оно ниже того, что вы ищете, перейдите на 750.Если оно выше того, что вы ищете, перейдите на 250.Затем вы повторяете процесс, пока не найдете свое значение (и ключ).Каждый раз, когда мы переходим половину пространства поиска, мы можем отбросить проверку многих других значений, поскольку мы знаем, что число 3004 не может быть больше числа 5000 (помните, что это отсортированный список).

n log(n) тогда означает n * log(n).

Я попытаюсь написать объяснение для настоящего восьмилетнего мальчика, не прибегая к техническим терминам и математическим понятиям.

Например, что именно O(n^2) операцию делать?

Если вы находитесь в вечеринке, и есть n люди в группе, включая вас.Сколько нужно рукопожатий, чтобы все пожали друг другу руки, учитывая, что люди, вероятно, в какой-то момент забудут, кому они пожимали руки?

Примечание:это приближение к симплексу, дающее n(n-1) что достаточно близко к n^2.

И что, черт возьми, это значит, если операция O(n log(n))?

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

Примечание:это даст n * log n to the base 10.

И нужно ли кому-то курить крэк, чтобы написать O(x!)?

Вы богатый ребенок, и в вашем гардеробе много одежды, есть x ящики для каждого типа одежды, ящики расположены рядом друг с другом, в первом ящике 1 предмет, в каждом ящике столько же тканей, сколько в ящике слева от него, и еще один, поэтому у вас есть что-то вроде 1 шапка, 2 парики, .. (x-1) штаны, тогда x рубашки.А теперь сколькими способами можно нарядиться, используя по одному предмету из каждого ящика.

Примечание:этот пример показывает, сколько листьев в дереве решений, где number of children = depth, что осуществляется посредством 1 * 2 * 3 * .. * x

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top