Как можно узнать, какую нотацию анализа сложности времени использовать?

https://cs.stackexchange.com/questions/57

16-10-2019
|

Вопрос

В большинстве вступительных классов алгоритма представлены такие нотации, как $ o $ (Big O) и $ theta $, и студент, как правило, научится использовать один из них, чтобы найти сложность времени.

Тем не менее, есть и другие обозначения, такие как $ o $, $ omega $ и $ omega $. Существуют ли какие -либо конкретные сценарии, в которых одна нотация была бы предпочтительной для другого?

Решение

Вы имеете в виду Нотация Ландау. Анкет Они не являются разными символами для одного и того же, но имеют совершенно разные значения. Который является «предпочтительным», полностью зависит от желаемого заявления.

$ f in cal {o} (g) $ означает, что $ f $ растет максимум до $ g $, асимптотически и до постоянного фактора; Думайте об этом как о $ leq $. $ f in o (g) $ - более строгая форма, то есть $ <$.

$ f in omega (g) $ имеет симметричное значение: $ f $ растет как минимум столько же, как $ g $. $ Omega $ - его более строгий двоюродный брат. Вы можете видеть, что $ f in omega (g) $ эквивалентно $ g in cal {o} (f) $.

$ f in theta (g) $ означает, что $ f $ растет примерно так же быстро, как $ g $; Формально $ f in cal {o} (g) cap omega (g) $. $ f sim g $ (асимптотическое равенство) - его более сильная форма. Мы часто имеем в виду $ theta $, когда используем $ cal {o} $.

Обратите внимание, как $ cal {o} (g) $ и его братья и сестры Функциональные классы. Анкет Важно очень знать об этом и их точных определениях, которые могут отличаться в зависимости от того, кто говорит, - при выполнении «арифметики» с ними.

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

Предлагаемое чтение:

Если вы заинтересованы в том, чтобы использовать нотацию Ландау строго и здраво, вы можете быть заинтересованы в недавней работе Rutanen et al. [1]. Они формулируют необходимые и достаточные критерии для асимптотических обозначений, поскольку мы используем их в алгоритмиках, показывают, что общее определение не соответствует им и предоставляет (фактически) работоспособное определение.

Общее определение Ontation для анализа алгоритма К. Рутанен и соавт. (2015)

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

Большой О: верхняя граница

«Big O» ($ O $), безусловно, является наиболее распространенным. Когда вы анализируете сложность алгоритма, большую часть времени важно иметь некоторую верхнюю границу того, как быстро растет время выполнения, когда растет размер входа. По сути, мы хотим знать, что управление алгоритмом не займет «слишком долго». Мы не можем выразить это в реальных единицах времени (секунды), потому что это будет зависеть от точной реализации (как написана программа, насколько хорош компилятор, насколько быстро процессор машины,…). Таким образом, мы оцениваем то, что не зависит от таких деталей, а это сколько еще требуется, чтобы запустить алгоритм, когда мы кормим его большим вводом. И в основном мы заботимся, когда мы можем быть уверены, что программа будет выполнена, поэтому мы обычно хотим знать, что это займет такое и такое количество времени или меньше.

Сказать, что алгоритм имеет время выполнения $ O (f (n) $ для размера ввода $ n $ означает, что существует некоторая постоянная $ k $, так что алгоритм завершается в максимум $ k , f (n ) $ шаги, то есть время работы алгоритма растет не так же быстро, как $ f $ (до коэффициента масштабирования). Отмечая $ t (n) $ время выполнения алгоритма для размера ввода $ n $, $ o (n) $ неформально означает, что $ t (n) le f (n) $ до некоторого фактора масштабирования.

Нижняя граница

Иногда полезно иметь больше информации, чем верхняя граница. $ Omega $ - это обратное значение $ o $: он выражает, что функция растет как минимум так же быстро, как и другая. $ T (n) = omega (g (n)) $ означает, что $ t (n) ge k 'g (n) $ для некоторой постоянной $ k' $ или для неофициального выражения, $ t (n) ge g (n) $ до некоторого фактора масштабирования.

Когда время выполнения алгоритма может быть определено точно, $ theta $ объединяет $ o $ и $ omega $: он выражает, что скорость роста функции известна, вплоть до коэффициента масштабирования. $ T (n) = theta (h (n)) $ означает, что $ k h (n) ge t (n) ge k 'h (n) $ для некоторых констант $ k $ и $ k' $. Неофициально говоря, $ t (n) abx h (n) $ до некоторого фактора масштабирования.

Дальнейшие соображения

«Маленькие» $ o $ и $ Omega $ используются гораздо реже в анализе сложности. Little $ o $ сильнее, чем Big $ o $; Если $ o $ указывает на рост, который не более быстрее, $ o $ указывает на то, что рост строго медленнее. И наоборот, $ Omega $ указывает на строго более быстрый рост.

Я был немного неформальным в обсуждении выше. Википедия имеет формальные определения и более математический подход.

Имейте в виду, что использование равного знака в $ t (n) = o (f (n)) $, а то же самое является неправильным. Строго говоря, $ o (f (n) $ - это набор функций переменной $ n $, и мы должны написать $ t in o (f) $.

Пример: некоторые алгоритмы сортировки

Поскольку это довольно сухо, позвольте мне привести пример. Большинство алгоритмов сортировки имеют квадратичное время выполнения наихудшего случая, т.е. для ввода размера $ n $, время выполнения алгоритма - $ O (n^2) $. Например, Выбор сортировки Имеет время выполнения $ o (n^2) $, потому что для выбора элемента $ k $ th требуется сравнения $ nk $, на общую сумму сравнения $ n (n-1)/2 $. Фактически, количество сравнений всегда $ n (n-1)/2 $, которое растет как $ n^2 $. Таким образом, мы можем быть более точными в отношении сложности времени отбора: это $ theta (n^2) $.

Теперь возьми Сортировка слиянием. Анкет Сорт слияния также квадратично ($ O (n^2) $). Это правда, но не очень точное. Сорт -сортировка на самом деле имеет время выполнения $ O (n : mathrm {lg} (n)) $ в худшем случае. Как сортировка выбора, рабочая поток Merge Sort по существу не зависит от формы ввода, и его время выполнения всегда - $ n : mathrm {lg} (n) $ до постоянного мультипликационного фактора, то есть, это $ theta (n : mathrm {lg} (n)) $.

Далее, рассмотрим Quicksort. Анкет QuickSort более сложный. Это, безусловно, $ O (n^2) $. Кроме того, худший случай QuickSort квадратично: худший случай $ theta (n^2) $. Тем не менее, лучший случай QuickSort (когда вход уже отсортирован) является линейным: лучшее, что мы можем сказать для более низкого границы с QuickSort в целом, - это $ Omega (n) $. Я не буду повторять доказательство здесь, но средний сложность QuickSort (среднее значение, принятое на все возможные перестановки ввода) - это $ theta (n : mathrm {lg} (n)) $.

Существуют общие результаты по сложности алгоритмов сортировки в общих условиях. Предположим, что алгоритм сортировки может сравнивать только два элемента за раз, с результатом «да или нет» (либо $ x le y $, либо $ x> y $). Тогда очевидно, что время работы любого алгоритма сортировки всегда является $ omega (n) $ (где $ n $ - это количество элементов для сортировки), потому что алгоритм должен сравнивать каждый элемент хотя бы раз, чтобы узнать, где он подойдет. Анкет Эта нижняя граница может быть выполнена, например, если ввод уже отсортирован, а алгоритм просто сравнивает каждый элемент со следующим и поддерживает их в порядке (это сравнение $ n-1 $). Что менее очевидно, так это то, что максимум Время работы обязательно $ omega (n : mathrm {lg} (n)) $. Вполне возможно, что алгоритм иногда будет проводить меньше сравнений, но должен быть некоторый постоянный $ k $, так что для любого размера ввода $ n $ есть как минимум один вход, на котором алгоритм делает более $ k n mathrm { lg} (n) $ сравнения. Идея доказательства состоит в том, чтобы построить дерево решений алгоритма, то есть следовать решениям, которые алгоритм принимает из результата каждого сравнения. Поскольку каждое сравнение возвращает результат «да или нет», дерево решений является бинарным деревом. Существуют возможные перестановки входов, и алгоритм должен различать их все, поэтому размер дерева решений - $ n! $. Поскольку дерево является двоичным деревом, оно требует глубины $ theta ( mathrm {lg} (n!)) = Theta (n : mathrm {lg} (n)) $, чтобы соответствовать всем этим узлам. Глубина - это максимальное количество решений, которые принимает алгоритм, поэтому запуск алгоритма включает в себя по крайней мере столько сравнений: максимальное время выполнения - $ omega (n : mathrm {lg} (n)) $.

¹ _{Или другое потребление ресурсов, такое как пространство памяти. В этом ответе я рассматриваю только время работы.}

Как правило, $ o $ используется для указания верхних связей (оценка сверху), в то время как $ Omega $ используется для указания нижних связей (оценка снизу), а $ theta $ используется при совпадении, в котором, в котором, в котором есть Случай вы можете использовать $ theta $ вместо их (обычно), чтобы указать результат.

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

Не связан с cs.stackexchange