Как рассчитать «n» для разных обозначений Big O, Omega, Litle o, Litle omega и Theta Notation

Question

Я изучаю алгоритмы, но вычисления, чтобы найти Time Complexity, не так уж и легки для меня, трудно запомнить когда использовать log n, n log n, n^2, n^3, 2n и т. д., мое сомнение заключается в том, как рассматривать эти входные функции при вычислении сложности, является ли их конкретным способом вычисления сложности, например, используя для цикла возьмем эту сложность всегда и так далее ....?

Answer 1

Log (N): при использовании рекурсии и дерево генерируется использование журнал (п). я имею в виду разделяя и властвуя когда вы ныряете проблемы в 2-половинок на самом деле вы генерирующие рекурсивного дерева.

его сложность Журнал (n), почему? потому что это двоичное дерево в природе и для двоичного дерева, мы используем Log (Base2) (n).

попробуйте себя: предположим, что n = 4 (элементы), поэтому log (base2) (4) = 2, вы разделите его на равную половину.

nLog (n): запомнить Журнал (n) его разделение до одного элемента. после этого вы начинаете слияние отсортированных элементов, которые принимают время лайнера

других слова Объединения элементов имеет сложность «п» так общая сложность будет п (Слияние) + Log (п) (Деление), который, наконец, стал nLog (n).

п^2: , когда вы видите, проблема решается в двух вложенных циклов, то Сложность п^2. i.e Матрицы/2-D массивы, которые они вычисляли в 2 циклах. одна петля внутри внешнего контура.

n^3: oh 3-D массивы, это для 3 вложенных циклов. цикл внутри цикла внутри цикла.

2n: спасибо, что вы не забыли написать «2» с этим «n», иначе я забыл объяснить это.

так «2» здесь с «п» постоянен просто игнорировать его. Зачем ?. потому что, если вы путешествуете в другой город AIR. вы засчитываете только часы, которые выполняете полет, а не часы, потребляемые при достижении порта AIR. Я имею в виду, что это минор, мы удаляем константу.

и «п» просто помните это слово «Linear»Большой т.е.-O (п) линейная сложность. К сожалению, я обнаружил, что нет алгоритма, который сортирует элементы в Линейном времени. т.е. просто в одном цикле (обход одного массива).

Что нужно помнить:

Номинальное время: Линейное время, сложность Big-O (п)

полиномиальное время: Не Линейное время, сложность Big-O [журнал (п), nlog (n), n^2, n^3, n^4, n^5).

Время Экспоненциальный: 2^п, п^п, то есть эта проблема будет решить за экспоненциальное время т.е. N^мощности (п) (Это плохо плохо плохо, не называется алгоритм)

Answer 2

Существует множество ссылок на то, как грубо рассчитать Big O и сложность его брата, но нет истинной формулы.

Однако есть рекомендации, которые помогут вам рассчитать сложность, такую ​​как представленные ниже. Я предлагаю рассмотреть как можно больше различных программ и структур данных, чтобы помочь вам ознакомиться с шаблоном и просто изучить, изучить, изучить, пока не получите его! Есть образец, и вы увидите его, тем больше вы его изучаете.

Источник: http://www.dreamincode.net/forums/topic/125427-determining-big-o-notation/

1. Вложенные циклы перемножаются.
2. Добавлены последовательные циклы.
3. Сохраняется только самый большой термин, все остальные отбрасываются.
4. Константы отбрасываются.
5. Условные проверки являются постоянными (то есть 1).