Big-O для восьмилетних?

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

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

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

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

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

Можно подумать об этом так:

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

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

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

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

Кроме того, в масштабе LogY / LogX все функции n^1/2, n, n² выглядят как прямые линии, в то время как в масштабе LogY / X 2ⁿ, eⁿ, 10ⁿ являются прямыми линиями, а п! является линефмическим (выглядит как п войти п).

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

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

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

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

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

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

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

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

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

Итак, настоящая сделка - ж (п). Если ж вообще не растет с п, например ж (п) = 1, тогда вы будете масштабироваться фантастически - ваше время работы всегда будет просто А + B. Если ж растет линейно с п, то есть ж (п) = п, ваше время работы будет масштабироваться настолько хорошо, насколько можно ожидать - если ваши пользователи ждут 10 нс для 10 элементов, они будут ждать 10000 нс для 10000 элементы (без учета аддитивной константы). Но если он растет быстрее, как п², тогда у вас проблемы; вещи начнут слишком сильно замедляться, когда вы получите большие коллекции. ж (п) = п log (п) обычно является хорошим компромиссом: ваша операция не может быть настолько простой, чтобы дать линейное масштабирование, но вам удалось урезать вещи так, что он масштабируется намного лучше, чем ж (п) = п².

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

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

Мне нравится ответ Дона Нойфельда, но я думаю, что могу добавить кое-что о 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 в классах математики в старших классах, хотя я считаю эту идею довольно эксцентричной.

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

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

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

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

Если вместо этого мы хотим сказать, что функция растет так же быстро, как какая-либо другая функция, мы используем тета, чтобы указать на это (я напишу T (f (n)), чтобы обозначать \ Theta 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 (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, так что постоянные множители и т. д. Дают реальную значительную разницу.

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

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

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

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

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

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

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

Я думаю об этом так: у вас есть задача устранить проблему, вызванную каким-то злым злодеем V, который выбирает 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) или даже хуже. Теоретически невозможно для любого компьютера вычислить правильный ответ - даже если вы используете каждую частицу во Вселенной в качестве вычислительного элемента, выполняющего операцию за минимально возможное время для жизни Вселенной, у вас все равно останется много нулей . (Другой вопрос, сможет ли квантовый компьютер решить эту проблему.)

Думайте об этом как о штабелировании блоков лего (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 - количество уложенных блоков.

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

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

• И разве нужно курить крэк, чтобы написать О (х!)?

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

"Интуиция" за 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), поскольку в конечном итоге он проходит его и оставляет его навсегда.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я пытаюсь объяснить, приводя простые примеры кода на 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²) выглядит как

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

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

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

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

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

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

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

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

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

Like what exactly would an O(n^2) operation do?

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

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

And what the heck does it mean if an operation is O(n log(n))?

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

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

And does somebody have to smoke crack to write an O(x!)?

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

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