Вопрос по algorithm – Big-O для восьмилетних? [Дубликат]

294

This question already has an answer here:

What is a plain English explanation of “Big O” notation? 39 answers

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

Like what exactly would an O(n^2) operation do? And what the heck does it mean if an operation is O(n log(n))? And does somebody have to smoke crack to write an O(x!)?
На этот вопрос ответили очень хорошо, поэтому я не буду беспокоиться. Я просто хотел сказать, что я люблю название вашего вопроса! Использование концепции о том, что вы что-то не понимаете, пока не сможете объяснить это 8-летнему, - отличный способ сформулировать вопрос. TMarshall
Разве название не будет лучше сформулировано, как, скажем, «Что такое простое объяснение Big-O?» И т. Д. Chris
@bradtgmurray: или рейтинг PG ... Robert S Ciaccio
@TMarshall Это может быть интересный заголовок, но это не означает, что он обязательно доступен для поиска. bradtgmurray
Когда я прочитал это, я подумал, что вы говорите о:en.wikipedia.org/wiki/The_Big_O Alex

Ваш Ответ

25   ответов
1

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

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

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

70

am математик.)

Если что то О (f(n)), то время работыn элементы будут равныA f(n) + B  (измеряется, скажем, в тактах или процессорах ЦП). Это ключ к пониманию того, что у вас также есть эти константыA а такжеB, которые возникают из конкретной реализации.B представляет по существу «постоянные накладные расходы»; вашей операции, например, некоторая предварительная обработка, которую вы выполняете, которая не зависит от размера коллекции.A представляет скорость вашего фактического алгоритма обработки предметов.

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

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

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

O(1): retrieving an element from an array. We know exactly where it is in memory, so we just go get it. It doesn't matter if the collection has 10 items or 10000; it's still at index (say) 3, so we just jump to location 3 in memory. O(n): retrieving an element from a linked list. Here, A = 0.5, because on average you''ll have to go through 1/2 of the linked list before you find the element you're looking for. O(n2): various "dumb" sorting algorithms. Because generally their strategy involves, for each element (n), you look at all the other elements (so times another n, giving n2), then position yourself in the right place. O(n log(n)): various "smart" sorting algorithms. It turns out that you only need to look at, say, 10 elements in a 1010-element collection to intelligently sort yourself relative to everyone else in the collection. Because everyone else is also going to look at 10 elements, and the emergent behavior is orchestrated just right so that this is enough to produce a sorted list. O(n!): an algorithm that "tries everything," since there are (proportional to) n! possible combinations of n elements that might solve a given problem. So it just loops through all such combinations, tries them, then stops whenever it succeeds.
Error: User Rate Limit ExceededO(f(n))Error: User Rate Limit ExceededA f(n) + B.
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded:-)
Error: User Rate Limit Exceeded
1

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

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

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

108

Big O Analysis

Кроме того, наLogY/LogX масштабировать функции n1/2, n, n2  все выглядят какпрямые линиив то время как наLogY/X масштаб 2n, en, 10n  прямые линии иn! является линейным (выглядит какn log n).

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
2

вании через них.

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

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

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

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

12

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

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

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

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

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

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

5

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

O (1) - & gt; увеличение N действительно не имеет никакого значения вообще

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

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

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

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
2

но я думаю, что могу добавить кое-что о O (n log n).

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

Если вы посмотрите на алгоритмы быстрой сортировки или сортировки слиянием, то увидите, что они оба используют метод деления списка, который будет отсортирован пополам, сортировки каждой половины (с использованием одного и того же алгоритма, рекурсивно), а затем рекомбинацию двух половин. Такого родаrecursive стратегия разделяй и властвуй будет 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). Mergesort строит другой путь, начиная с n рекомбинаций из 1 элемента и заканчивая 1 рекомбинацией из n элементов, где рекомбинация двух отсортированных списков равна O (n).

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

помните, что log n означает log-base-2 of n. Затем посмотрите на каждую часть:

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
21

емого, например, тасования карт.

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

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

1

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

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

257

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

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 секунды, по сравнению с часами.

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

clarification: На самом деле, 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
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
18

За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;

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

..amazing can u please also add code on how to overcome greater complexity with lower.. this will be helpful .. – Vishal Sharma Nov 18 '13 at 7:37
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
3

The "Intuitition" behind Big-O

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

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

Так, например, если для каждого x & gt; 100 вы видите, что f (x) & gt; g (x), тогда f (x) "быстрее" чем г (х).

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

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

1

я отвечал на вопрос так же, как на 8-летнего ребенка.

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

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

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

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

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

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

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

0

него мальчика, кроме технических терминов и математических понятий.

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededhow many times, how many digits are in the number of the players n.Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
286

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
2

Programming Pearls) покрывать такие вещи действительно прагматично.Этот разговор данный им включает в себя один такой анализ быстрой сортировки.

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

0

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

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

4

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

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

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

58

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

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

O(1) "constant time" - the time required is independent of the size of the input. As a rough category, I would include algorithms such as hash lookups and Union-Find here, even though neither of those are actually O(1). O(log(n)) "logarithmic" - it gets slower as you get larger inputs, but once your input gets fairly large, it won't change enough to worry about. If your runtime is ok with reasonably-sized data, you can swamp it with as much additional data as you want and it'll still be ok. O(n) "linear" - the more input, the longer it takes, in an even tradeoff. Three times the input size will take roughly three times as long. O(n log(n)) "better than quadratic" - increasing the input size hurts, but it's still manageable. The algorithm is probably decent, it's just that the underlying problem is more difficult (decisions are less localized with respect to the input data) than those problems that can be solved in linear time. If your input sizes are getting up there, don't assume that you could necessarily handle twice the size without changing your architecture around (eg by moving things to overnight batch computations, or not doing things per-frame). It's ok if the input size increases a little bit, though; just watch out for multiples. O(n^2) "quadratic" - it's really only going to work up to a certain size of your input, so pay attention to how big it could get. Also, your algorithm may suck -- think hard to see if there's an O(n log(n)) algorithm that would give you what you need. Once you're here, feel very grateful for the amazing hardware we've been gifted with. Not long ago, what you are trying to do would have been impossible for all practical purposes. O(n^3) "cubic" - not qualitatively all that different from O(n^2). The same comments apply, only more so. There's a decent chance that a more clever algorithm could shave this time down to something smaller, eg O(n^2 log(n)) or O(n^2.8...), but then again, there's a good chance that it won't be worth the trouble. (You're already limited in your practical input size, so the constant factors that may be required for the more clever algorithms will probably swamp their advantages for practical cases. Also, thinking is slow; letting the computer chew on it may save you time overall.) O(2^n) "exponential" - the problem is either fundamentally computationally hard or you're being an idiot. These problems have a recognizable flavor to them. Your input sizes are capped at a fairly specific hard limit. You'll know quickly whether you fit into that limit.

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

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

O(1) - you're only looking at most at a fixed-size chunk of your input data, and possibly none of it. Example: the maximum of a sorted list. Or your input size is bounded. Example: addition of two numbers. (Note that addition of N numbers is linear time.) O(log n) - each element of your input tells you enough to ignore a large fraction of the rest of the input. Example: when you look at an array element in binary search, its value tells you that you can ignore "half" of your array without looking at any of it. Or similarly, the element you look at gives you enough of a summary of a fraction of the remaining input that you won't need to look at it. There's nothing special about halves, though -- if you can only ignore 10% of your input at each step, it's still logarithmic. O(n) - you do some fixed amount of work per input element. (But see below.) O(n log(n)) - there are a few variants. You can divide the input into two piles (in no more than linear time), solve the problem independently on each pile, and then combine the two piles to form the final solution. The independence of the two piles is key. Example: classic recursive mergesort. Each linear-time pass over the data gets you halfway to your solution. Example: quicksort if you think in terms of the maximum distance of each element to its final sorted position at each partitioning step (and yes, I know that it's actually O(n^2) because of degenerate pivot choices. But practically speaking, it falls into my O(n log(n)) category.) O(n^2) - you have to look at every pair of input elements. Or you don't, but you think you do, and you're using the wrong algorithm. O(n^3) - um... I don't have a snappy characterization of these. It's probably one of: You're multiplying matrices You're looking at every pair of inputs but the operation you do requires looking at all of the inputs again the entire graph structure of your input is relevant O(2^n) - you need to consider every possible subset of your inputs.

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
5

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

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

18

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

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

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

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

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

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

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

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

Ванильная быстрая сортировка, как всегда, хороший пример. Это 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)) и heapsort (средняя стоимость T (n.log n)) являются алгоритмами сортировки с одинаковыми средними затратами, однако быстрая сортировка обычно намного быстрее, чем heapsort. Это связано с тем, что heapsort выполняет на несколько элементов больше сравнений, чем quicksort.

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededpotentialError: User Rate Limit ExceededcurrentError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы