Большой-O для восьми лет? [дубликат]
В Java все переменные, которые вы объявляете, на самом деле являются «ссылками» на объекты (или примитивы), а не самими объектами.
При попытке выполнить один метод объекта , ссылка просит живой объект выполнить этот метод. Но если ссылка ссылается на NULL (ничего, нуль, void, nada), то нет способа, которым метод будет выполнен. Тогда runtime сообщит вам об этом, выбросив исключение NullPointerException.
Ваша ссылка «указывает» на нуль, таким образом, «Null -> Pointer».
Объект живет в памяти виртуальной машины пространство и единственный способ доступа к нему - использовать ссылки this. Возьмем этот пример:
public class Some {
private int id;
public int getId(){
return this.id;
}
public setId( int newId ) {
this.id = newId;
}
}
И в другом месте вашего кода:
Some reference = new Some(); // Point to a new object of type Some()
Some otherReference = null; // Initiallly this points to NULL
reference.setId( 1 ); // Execute setId method, now private var id is 1
System.out.println( reference.getId() ); // Prints 1 to the console
otherReference = reference // Now they both point to the only object.
reference = null; // "reference" now point to null.
// But "otherReference" still point to the "real" object so this print 1 too...
System.out.println( otherReference.getId() );
// Guess what will happen
System.out.println( reference.getId() ); // :S Throws NullPointerException because "reference" is pointing to NULL remember...
Это важно знать - когда больше нет ссылок на объект (в пример выше, когда reference и otherReference оба указывают на null), тогда объект «недоступен». Мы не можем работать с ним, поэтому этот объект готов к сбору мусора, и в какой-то момент VM освободит память, используемую этим объектом, и выделит другую.
23 ответа
Один образ мыслей об этом - это:
O (N^2) означает для каждого элемента, Вы делаете что-то с любым элементом, таким как сравнение их. Пузырьковая сортировка является примером этого.
O (N регистрируют N) средства для каждого элемента, Вы делаете что-то, что только должно посмотреть на журнал N элементов. Это обычно, потому что Вы знаете что-то об элементах, которые позволяют Вам сделать эффективный выбор. Большинство эффективных видов является примером этого, таким как сортировка слиянием.
O (N!) означает делать что-то для всех возможных перестановок элементов N. Коммивояжер является примером этого, где существуют N! способы посетить узлы и решение для грубой силы состоят в том, чтобы посмотреть на общую стоимость каждой возможной перестановки для нахождения оптимальной.
журнал (n) означает логарифмический рост. Пример был бы делением и завоевал бы алгоритмы. Если у Вас есть 1 000 отсортированных чисел в массиве (напр. 3, 10, 34, 244, 1203...), и хочу искать число в списке (найдите его положение), Вы могли запустить с проверки значения числа в индексе 500. Если это ниже, чем, что Вы ищете, переход к 750. Если это выше, чем, что Вы ищете, переход к 250. Тогда Вы повторяете процесс, пока Вы не находите свое значение (и ключ). Каждый раз, когда мы переходим половина пространства поиска, мы можем отобрать далеко тестирование многих других значений, так как мы знаем, что номер 3004 не может быть выше номера 5000 (помните, это - отсортированный список).
журнал n (n) тогда означает n * журнал (n).
Только ответить на несколько комментариев к моему выше сообщения:
Domenic - я нахожусь на этом сайте, и я забочусь. Не для пользы педантизма, но потому что мы - как программисты - обычно заботимся о точности. Используя O () нотация неправильно в стиле, который некоторые сделали здесь, представляет его довольно бессмысленный; мы можем точно также сказать, что что-то берет единицы времени n^2 в качестве O (n^2) в соответствии с соглашениями, используемыми здесь. Используя O () ничего не добавляет. Это не просто маленькое несоответствие между общим использованием и математической точностью, о которой я говорю, вот в чем разница между ним являющийся значимым и этим нет.
я знаю многих, многие превосходные программисты, которые используют эти термины точно. Говоря, 'о, мы - программисты поэтому, мы не заботимся', унижает целое предприятие.
onebyone - ну, не действительно, хотя я беру Вашу точку. Это не O (1) для произвольно большого n, который является видом определения O (). Это просто идет, чтобы показать, что O () ограничил применимость для ограниченного n, где мы на самом деле говорили бы о количестве сделанных шагов, а не привязанный то число.
Для понимания O (n регистрируют n) помните, что журнал n означает log-base-2 n. Тогда посмотрите на каждую часть:
O (n), более или менее, когда Вы воздействуете на каждый объект в наборе.
O (регистрируют n) - когда количество операций совпадает с экспонентой, до которой Вы повышаете 2, для получения количества объектов. Двоичный поиск, например, должен сократить набор в половине журнала n времена.
O (n регистрируют n) является комбинацией †“, Вы делаете что-то вроде двоичного поиска каждого объекта в наборе. Эффективные виды часто работают путем выполнения одного цикла на объект, и в каждом цикле, делающем хороший поиск, чтобы найти, что правильное место помещает объект или рассматриваемую группу. Следовательно n * регистрируют n.
Думайте о нем как складывающий lego блоки (n) вертикально и перепрыгивающий через них.
O (1) средства на каждом шаге, Вы ничего не делаете. Высота остается такой же.
O (n) означает на каждом шаге, Вы складываете c блоки, где c1 является константой.
O (n^2) означает на каждом шаге, Вы складываете блоки c2 x n, где c2 является константой, и n является количеством сложенных блоков.
O (nlogn) означает на каждом шаге, Вы складываете журнал c3 x n x n блоки, где c3 является константой, и n является количеством сложенных блоков.
Большинство книг Jon Bentley (например, Жемчуг Программирования ) касается такого материала действительно прагматическим способом. Этот разговор данный им включает один такой анализ quicksort.
, В то время как не совсем релевантный для вопроса, Knuth придумал интересная идея : обучение Нотации "большого О" в классах исчисления средней школы, хотя я нахожу эту идею довольно эксцентриковой.
Мне нравится ответ neufeld's Дона, но я думаю, что могу добавить, что-то о O (n регистрируют n).
алгоритм, который использует простое деление и завоевывает стратегию, вероятно, будет O (зарегистрируйте n). Самый простой пример этого находит что-то в отсортированном списке. Вы не запускаете вначале и сканируете для него. Вы переходите к середине, Вы решаете, необходимо ли тогда пойти назад или вперед, переход на полпути к последнему месту Вы смотрели, и повторите это, пока Вы не находите объект, который Вы ищете.
, Если Вы смотрите на quicksort или сортируете алгоритмы с объединением, Вы будете видеть, что они оба проявляют подход деления списка, который будет отсортирован в половине, сортировка каждой половины (использующий тот же алгоритм, рекурсивно), и затем повторно комбинирующий эти две половины. Этот вид рекурсивный делит и завоевывает стратегию, будет O (n, регистрируют n).
, Если Вы думаете об этом тщательно, Вы будете видеть, что quicksort делает O (n) разделение алгоритма на целых n объектах, затем O (n) делящий дважды на n/2 объектах, тогда 4 раза на n/4 объектах, и т.д...., пока Вы не добираетесь до n разделы на 1 объекте (который является вырожденным). Количество раз, которое Вы разделяете n пополам для получения к 1, является приблизительно журналом n, и каждый шаг является O (n), так рекурсивное деление, и завоюйте, O (n, регистрируют n). Сортировка с объединением создает другой путь, начиная с n перекомбинаций 1 объекта, и заканчивающийся с 1 перекомбинацией n объектов, где перекомбинация двух отсортированных списков является O (n).
Что касается курения трещины для записи O (n!) алгоритм, Вы - то, если у Вас нет выбора. Проблемой коммивояжера, данной выше, как полагают, является одна такая проблема.
Одна вещь, которая еще не была затронута по некоторым причинам:
, Когда Вы видите алгоритмы с вещами как O (2^n) или O (n^3) или другие противные значения, это часто означает, что Вы оказываетесь перед необходимостью принимать несовершенное решение своей проблемы для получения приемлемой производительности.
Правильные решения, которые аварийно завершаются как это, распространены при контакте с проблемами оптимизации. Почти корректный ответ, поставленный в разумный период времени, лучше, чем корректный ответ, поставленный еще долго после того, как машина затухла для чистки.
Рассматривают шахматы: Я не знаю точно, чем считается правильное решение, но это - вероятно, что-то как O (n^50) или еще хуже. Для любого компьютера теоретически невозможно на самом деле вычислить корректный ответ - даже при использовании каждой частицы во вселенной как вычислительный элемент, выполняющий операцию в минимальное возможное время для жизни вселенной, Вы все еще имеете много в запасе нулей. (Может ли квантовый компьютер решить его, другой вопрос.)
Путем я думаю об этом, Вы, имеют задачу чистки проблемы, вызванной некоторым злым злодеем V, кто выбирает N, и необходимо оценить, насколько дольше это собирается взять для окончания проблемы, когда он увеличивает N.
O (1)-> увеличивающийся N действительно не имеет никакого значения во всем
O (журнал (N))->, каждый раз V удваивает N, необходимо провести дополнительное количество времени T для выполнения задачи. V удваивает N снова, и Вы тратите ту же сумму.
O (N)-> каждый раз V удваивает N, Вы проводите вдвое больше времени.
O (N^2)-> каждый раз V удваивает N, Вы тратите 4x столько же времени. (это не справедливо!!!)
O (N журнал (N))-> каждый раз V удваивает N, Вы проводите вдвое больше времени плюс немного больше.
Это границы алгоритма; программисты хотят описать, сколько времени это собирается взять для больших значений N. (который становится важным, когда Вы учитываете числа, которые используются в криптографии - если компьютеры убыстряются фактором 10, насколько больше битов необходимо использовать, чтобы гарантировать, что им все еще потребуются 100 лет для повреждения шифрования и не всего 1 год?)
Некоторые границы могут иметь странные выражения, если это имеет значение для вовлеченных людей. Я видел материал как O (N журнал (N) журнал (журнал (N))) где-нибудь в Искусстве Knuth Программирования для некоторых алгоритмов. (не может помнить который первое, что пришло на ум)
Нет, O (n) алгоритм не означает, что это выполнит операцию на каждом элементе. Нотация "большого О" дает Вам способ говорить о "скорости" Вас алгоритм, независимый от Вашей фактической машины.
O (n) означает, что время, которое займет Ваш алгоритм, растет линейно как Ваше входное увеличение. O (n^2) означает, что время, которое занимает Ваш алгоритм, растет как квадрат Вашего входа. И т.д.
Хорошо - существуют некоторые очень хорошие ответы здесь, но почти все они, кажется, делают ту же ошибку, и это - то, которое проникает в общее использование.
Неофициально, мы пишем, что 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, таким образом, это не очень трудно связанный, но это - все еще связанное законное.
, Почему, мы (программисты) используем границы вместо того, чтобы быть точными? Поскольку a) границы часто легче доказать и b) это дает нам стенографию для выражения свойств алгоритмов. Если я говорю, что мой новый алгоритм является O (n.log n), который означает, что в худшем случае его время выполнения будет ограничено сверху n.log n на исходных данных n для достаточно большого n (хотя видят мои комментарии ниже о том, когда я не мог бы иметь в виду худший случай).
, Если вместо этого, мы хотим сказать, что функция растет точно так же быстро как некоторая другая функция, мы используем тета для высказывания того мнения (я запишу T (f (n)) для значения \Theta f (n) в скидке с цены). T (g (n)) стенография для того, чтобы быть ограниченным от [1 120] выше и ниже 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!)?' Ответ нет - потому что в основном все, что Вы пишете, будет ограничено сверху функцией факториала. Время выполнения quicksort является O (n!) - это - просто не связанное трудное.
существует также другой размер тонкости здесь. Обычно мы говорим о , худший случай ввел , когда мы используем O (g (n)) нотация, так, чтобы мы сделали составной оператор: в худшее время выполнения случая это не будет немного хуже, чем алгоритм, который берет g (n) шаги, снова масштабирование по модулю и для достаточно большого n. Но иногда мы хотим говорить о времени выполнения среднее число и даже лучший случаи.
Ваниль quicksort является, как всегда, хорошим примером. Это - T (n^2) в худшем случае (это на самом деле сделает, по крайней мере, шаги n^2, но не значительно больше), но T (n.log n) в среднем случае, который должен сказать, что ожидаемое количество шагов пропорционально n.log n. В лучшем случае это также T (n.log n) - но Вы могли улучшить это для примером, проверив, был ли массив уже отсортирован, в этом случае, лучшее время выполнения случая было бы T (n).
, Как это касается Вашего вопроса о практической реализации этих границ? Ну, к сожалению, O () нотация скрывает константы, с которыми должны иметь дело реальные реализации. Таким образом, хотя мы можем сказать, что, например, для T (n^2) операция должны посетить каждую возможную пару элементов, мы не знаем, сколько раз мы должны посетить их (за исключением того, что это не функция n). Таким образом, нам придется посетить каждую пару 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)) и пирамидальная сортировка (средняя стоимость T (n.log n)) оба сортируют алгоритмы с той же средней стоимостью - все же quicksort, обычно намного быстрее, чем пирамидальная сортировка. Это вызвано тем, что пирамидальная сортировка делает еще несколько сравнений на элемент, чем quicksort.
Нельзя сказать, что O () нотация бесполезен, просто неточен. Это - настоящий тупой инструмент для владения для маленького n.
(Как заключительное примечание к этому трактату, помните, что O () нотация просто описывает рост любой функции - должно не обязательно быть время, это могла быть память, сообщения, которыми обмениваются в распределенной системе или количестве центральных процессоров, требуемых для параллельного алгоритма.)
Многие из них легки продемонстрировать с чем-то непрограммирование, как перестановка карт.
Сортировка деки карт путем прохождения через целой деки для нахождения туза лопат, затем прохождения через целой деки для нахождения 2 из лопат, и так далее была бы худшим случаем n^2, если бы дека была уже отсортирована назад. Вы посмотрели на все 52 карты 52 раза.
В целом действительно плохие алгоритмы являются не обязательно намеренными, они обычно - неправильное употребление чего-то еще, как вызов метода, который линеен в некотором другом методе, который повторяется по тому же набору линейно.
ответ don.neufeld очень хорош, но я, вероятно, объяснил бы это в двух частях: во-первых, существует грубая иерархия O (), в который падает большинство алгоритмов. Затем можно посмотреть на каждого из тех для предложения эскизов того, что типичный делают алгоритмы той временной сложности.
Практически, единственные O (), которые когда-либо, кажется, имеют значение:
- O (1) "постоянное время" - требуемое время независимо от размера входа. Как грубая категория, я включал бы алгоритмы, такие как поиски хеша и Нашел бы объединение здесь, даже при том, что ни один из тех не на самом деле O (1).
- O (журнал (n)) "логарифмический" - это становится медленнее, как Вы получаете большие исходные данные, но после того как Ваш вход становится довольно большим, он не изменится достаточно для волнения о. Если Ваше время выполнения соглашается с обоснованно измеренными данными, можно затопить его таким количеством дополнительных данных, как Вы хотите, и это все еще будет в порядке.
- O (n) "линейный" - чем более вход, тем дольше это берет в ровном компромиссе. Три раза входной размер возьмет примерно в три раза более длинный.
- O (n журнал (n)) "лучше, чем квадратичный" - увеличение входного вреда размера, но это все еще управляемо. Алгоритм, вероятно, достоин, это просто, что базовая проблема является более трудной (решения менее локализуются относительно входных данных), чем те проблемы, которые могут быть решены в линейное время. Если Ваши входные размеры встают там, не предполагайте, что Вы могли обязательно обработать дважды размер, не меняя Вашу архитектуру (например, движущимися вещами к ночным пакетным вычислениям, или не делая вещей на кадр). Хорошо, если входной размер увеличивается немного, хотя; просто не упустите кратные числа.
- O (n^2) "квадратичный" - это действительно только собирается работать до определенного размера Вашего входа, поэтому обратите внимание на то, как большой это могло добраться. Кроме того, Ваш алгоритм может высосать - думают трудно, чтобы видеть, существует ли O (n журнал (n)) алгоритм, который дал бы Вам, в чем Вы нуждаетесь. После того как Вы здесь, чувствуете себя очень благодарными за удивительные аппаратные средства, мы были одаренными. Недавно, то, что Вы пытаетесь сделать, было бы невозможно для всех практических целей.
- O (n^3) "кубический" - не качественно все, что отличающийся от O (n^2). Те же комментарии применяются, только больше. Существует достойный шанс, что более умный алгоритм мог бриться на этот раз вниз к чему-то меньшему, например, O (n^2 журнал (n)) или O (n^2.8...), но с другой стороны, существует хороший шанс, что это не будет стоить проблемы. (Вы уже ограничены в Вашем практическом входном размере, таким образом, постоянные множители, которые могут требоваться для более умных алгоритмов, вероятно, затопят свои преимущества для практических случаев. Кроме того, взгляды являются медленными; разрешение компьютеру пережевать его может сэкономить Вам время в целом.)
- O (2^n) "экспоненциал" - проблема или существенно в вычислительном отношении трудно, или Вы - идиот. Эти проблемы имеют распознаваемую разновидность им. Ваши входные размеры ограничиваются в довольно определенном жестком пределе. Вы будете знать быстро, вписываетесь ли Вы в тот предел.
И вот именно. Существует много других возможностей, которые соответствуют между ними (или больше, чем O (2^n)), но они не часто происходят на практике, и они качественно очень не отличаются от одного из них. Кубические алгоритмы уже являются чем-то вроде фрагмента; я только включал их, потому что я сталкивался с ними достаточно часто, чтобы стоить упомянуть (например, умножение матриц).
, Что на самом деле происходит для этих классов алгоритмов? Ну, я думаю, что у Вас было хорошее начало, хотя существует много примеров, которые не соответствовали бы этим характеристикам. Но для вышеупомянутого, я сказал бы, что оно обычно идет что-то как:
- O (1) - Вы только смотрите самое большее на блок фиксированного размера своих входных данных и возможно ни одного из него. Пример: максимум отсортированного списка.
- Или Ваш входной размер ограничен. Пример: добавление двух чисел. (Обратите внимание, что добавление чисел N является линейным временем.)
- O (регистрируют n) - каждый элемент Вашего входа говорит Вам достаточно игнорировать большую часть остальной части входа. Пример: при рассмотрении элемента массива в двоичном поиске его значение говорит Вам, что можно проигнорировать "половину" массива, не смотря ни на один из него. Или точно так же элемент, на который Вы смотрите, дает Вам действительно сводку части остающегося входа, что Вы не должны будете смотреть на него.
- нет ничего специального о половинах, хотя - если можно только проигнорировать 10% входа на каждом шаге, это все еще логарифмически.
- O (n) - Вы делаете некоторый установленный объем работы на входной элемент. (Но посмотрите ниже.)
- O (n журнал (n)) - существует несколько вариантов.
- можно разделить вход на две груды (в не больше, чем линейное время), решить проблему независимо на каждой груде и затем объединить две груды для формирования конечного решения. Независимость двух груд является ключевой. Пример: классическая рекурсивная сортировка с объединением.
- Каждая линейно-разовая передача по данным получает Вас на полпути к Вашему решению. Пример: quicksort, если Вы думаете с точки зрения максимального расстояния каждого элемента к его финалу, отсортировал положение на каждом шаге разделения (и да, я знаю, что это на самом деле O (n^2) из-за вырожденного выбора центра. Но в сущности это попадает в мой O (n журнал (n)) категория.)
- O (n^2) - необходимо посмотреть на каждую пару входных элементов.
- Или Вы не делаете, но Вы думаете, что делаете, и Вы используете неправильный алгоритм.
- O (n^3) - гм... У меня нет мгновенной характеристики их. Это - вероятно, один из:
- Вы умножаете матрицы
- , Вы смотрите на каждую пару исходных данных, но операция, которую Вы делаете, требует рассмотрения всех исходных данных снова
- , вся структура графика Вашего входа релевантна
- O (2^n) - необходимо рассмотреть каждое возможное подмножество исходных данных.
Ни один из них не строг. Особенно не линейные алгоритмы времени (O (n)): Я мог придумать много примеров, где необходимо посмотреть на все исходные данные, затем половина из них, затем половина из тех, и т.д. Или наоборот - Вы сворачиваете вместе пар исходных данных, затем рекурсивно вызываете вывод. Они не соответствуют описанию выше, так как Вы не смотрите на каждый вход однажды, но это все еще выходит в линейное время. Однако, 99,2% времени, линейное время означает смотреть на каждый вход однажды.
Это могло бы быть слишком математически, но здесь является моей попыткой. (Я математик.)
, Если что-то - O ( f ( n)), тогда это - время выполнения на n , элементы будут равны А f ( n) + B (измеренный в, скажем, тактах или операциях ЦП). Это является ключевым для понимания, что у Вас также есть эти константы А и B, которые являются результатом определенной реализации. B представляет по существу "постоянные издержки" Вашей операции, например, некоторой предварительной обработки, которую Вы делаете, который не зависит от размера набора. А представляет скорость Вашего фактического обрабатывающего объект алгоритма.
ключ, тем не менее, - то, что Вы используете большую нотацию O для выяснения , как хорошо что-то масштабируется . Таким образом, те константы не будут действительно иметь значения: при попытке выяснить, как масштабироваться от 10 до 10 000 объектов, кто заботится о константе, служебной B? Точно так же другие проблемы (см. ниже), конечно, перевесят вес мультипликативной константы А .
, Таким образом, реальное соглашение f ( n). Если f не вырастет нисколько с [1 117] n, например, f ( n) = 1, то Вы масштабируетесь фантастически---, Ваше время выполнения всегда просто будет А + B. Если f вырастет линейно с [1 123] n, т.е. f ( n) = n, то Ваше время выполнения масштабируется в значительной степени настолько лучше всего, как может ожидаться---, если Ваши пользователи будут ожидать 10 нс 10 элементов, они будут ожидать 10 000 нс 10 000 элементов (игнорирующий аддитивную постоянную). Но если это становится быстрее, как [1 127] <глоток> n 2 , тогда Вы в беде; вещи начнут замедляться слишком очень, когда Вы получите большие наборы. f ( n) = журнал n ( n) является хорошим компромиссом, обычно: Ваша операция не может быть столь простой, чтобы дать линейное масштабирование, но Вам удалось сократить вещи, таким образом, что это масштабируется намного лучше, чем [1 132] f ( n) = <глоток> n 2 .
Практически, вот некоторые хорошие примеры:
- O (1): получение элемента от массива. Мы знаем точно, где это находится в памяти, таким образом, мы просто идем, получают его. Не имеет значения, если набор имеет 10 объектов или 10000; это все еще в индексе (говорят) 3, таким образом, мы просто переходим к местоположению 3 в памяти.
- O ( n): получение элемента из связанного списка. Здесь, А = 0.5, потому что в среднем '' ll необходимо пройти 1/2 связанного списка перед нахождением элемента, который Вы ищете.
- O ( <глоток> n 2 ): различные "немые" алгоритмы сортировки. Поскольку обычно их стратегия включает для каждого элемента ( n), Вы смотрите на все другие элементы (так времена другой n, давая <глоток> n 2 ), затем положение сами в правильном месте.
- O ( журнал n ( n)): различные "умные" алгоритмы сортировки. Оказывается, что только необходимо посмотреть на, скажем, 10 элементов в 10 <глоток> 10 - набор элемента еще для интеллектуальной сортировки себя относительно [1 143] все в наборе. Поскольку все остальные также попытка посмотреть на 10 элементов, и поведение на стадии становления организуется просто право так, чтобы этого было достаточно для создания отсортированного списка.
- O ( n!): алгоритм, который "пробует все", с тех пор существует (пропорционален) n! возможные комбинации [1 147] n элементы, которые могли бы решить данную проблему. Таким образом, это просто циклы через все такие комбинации, пробует их, затем останавливается каждый раз, когда это успешно выполняется.
Вы могли бы найти полезным визуализировать его:
кроме того, на масштаб LogY/LogX функции n <глоток> 1/2 , n, n <глоток> 2 все похожи прямые линии , в то время как на [1 110] масштаб LogY/X 2 <глоток> n , e <глоток> n , 10 <глоток> n является прямыми линиями и n! linearithmic (похож n журнала n).
Большая вещь, которую Нотация "большого О" значит для Вашего кода, состоит в том, как это масштабируется при удвоении суммы "вещей", это воздействует на. Вот конкретный пример:
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
Так берут quicksort, который является O (n журнал (n)) по сравнению с пузырьковой сортировкой, которая является O (n^2). При сортировке 10 вещей quicksort в 3 раза быстрее, чем пузырьковая сортировка. Но при сортировке 100 вещей, это в 14 раз быстрее! Очевидно выбор самого быстрого алгоритма важен тогда. Когда Вы добираетесь до баз данных с миллионом строк, это может означать различие между Вашим запросом, выполняющимся через 0,2 секунды, по сравнению со взятием часов.
Другая вещь рассмотреть состоит в том, что плохой алгоритм является одной вещью, которой не может помочь Закон Гордона Мура. Например, если у Вас есть некоторое научное вычисление, это - O (n^3), и это может вычислить 100 вещей в день, удваивание скорости процессора только получает Вас 125 вещей за день. Однако удар, что вычисление к O (n^2) и Вы делаете 1 000 вещей в день.
разъяснение: На самом деле, Большой-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
Скажите, что ваш восьмилетний журнал (n) означает, сколько раз вам нужно нарезать длину n log за два чтобы получить размер n = 1: p
O (n log n) обычно сортирует O (n ^ 2) обычно сравнивает все пары элементов
- И нужно ли кому-нибудь курить, чтобы написать O (x!)?
Нет, просто используйте Пролог. Если вы пишете алгоритм сортировки в Прологе, просто описывая, что каждый элемент должен быть больше, чем предыдущий, и позволяя обратному отслеживанию выполнить сортировку за вас, это будет O (x!). Также известен как «сортировка перестановок».
«Интуиция» за Big-O
Imagine "соревнование" между двумя функциями по 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) всегда будет выигрывать в конце). Формальное определение также использует абсолютные значения. Но я надеюсь, что мне удалось сделать это интуитивно понятным.
Suppose you had a computer that could solve a problem of a certain size. Now imagine that we can double the performance a few times. How much bigger a problem can we solve with each doubling?
If we can solve a problem of double the size, that's O(n).
If we have some multiplier that isn't one, that's some sort of polynomial complexity. For example, if each doubling allows us to increase the problem size by about 40%, it's O(n^2), and about 30% would be O(n^3).
If we just add to the problem size, it's exponential or worse. For example, if each doubling means we can solve a problem 1 bigger, it's O(2^n). (This is why brute-forcing a cipher key becomes effectively impossible with reasonably sized keys: a 128-bit key requires about 16 quintillion times as much processing as a 64-bit.)
Я описываю это своим нетехническим друзьям так:
Рассмотрим сложение многозначных чисел. Старое доброе, карандашно-бумажное дополнение. То, что вы узнали, когда вам было 7-8 лет. Имея два трех- или четырехзначных числа, вы можете довольно легко узнать, к чему они складываются.
Если бы я дал вам два 100-значных числа и спросил вас, к чему они складываются, вычислить это было бы так: довольно просто, даже если вам пришлось использовать карандаш и бумагу. Смышленый ребенок может сделать такое дополнение буквально за несколько минут. Для этого потребуется всего около 100 операций.
Теперь рассмотрим многозначное умножение. Вы, вероятно, узнали об этом в возрасте 8 или 9 лет. Вы (надеюсь) проделали много повторяющихся упражнений, чтобы изучить механизм, лежащий в основе этого.
Теперь, представьте, что я дал вам те же два 100-значных числа и сказал вам умножить их вместе. Это будет намного, намного сложная задача, на которую у вас уйдут часы - и вряд ли вы обойдетесь без ошибок. Причина в том, что (эта версия) умножение равно O (n ^ 2); каждую цифру в нижнем числе нужно умножить на каждую цифру в верхнем числе, в результате останется около n ^ 2 операций. В случае 100-значных чисел это 10 000 умножений.
оставив в общей сложности около n ^ 2 операций. В случае 100-значных чисел это 10 000 умножений. оставив в общей сложности около n ^ 2 операций. В случае 100-значных чисел это 10 000 умножений.Помните басню о черепахе и зайце (черепахе и кролике)?
В долгосрочной перспективе побеждает черепаха, но в краткосрочной перспективе побеждает заяц.
Это например, O (logN) (черепаха) против O (N) (заяц).
Если два метода различаются своим большим O, то существует уровень N, на котором один из них выиграет, но большой O ничего не говорит о том, насколько велик этот N.
Я пытаюсь объяснить, приводя простые примеры кода на C #.
Для List
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!) Похоже, ммм, слишком устал, чтобы что-то придумать просто.
Но я надеюсь, что вы уловили суть дела?