Сложность времени Big-O

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

O (N):

for(int i = 0; i < n; i++) 
    sum++;

O (N^2):

for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) 
     sum++;

O (N^3):

for(int i = 0; i < n; i++) 
    for(int j = 0; j < n * n; j++) 
     sum++;

Я столкнулся с этими обозначениями, которые я не совсем понимаю. Как я могу привести примеры этих алгоритмов?

Может быть, я должен выразить это таким образом: написать алгоритм, который занимает много времени работает в пропорции:

O ((N^3)/4)
журнал п^3
O ((журнал^2) п) + О (п)
4^п
п^3/2

источник

2010-10-25 user471646

Вы так? См. Http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds и http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o и http : //stackoverflow.com/search?q = Big + O; –

Вопрос, как правило, вы найдете Big O для конкретного алгоритма, – medopal

Это ** примеры ** алгоритмов O(). Существует огромное количество алгоритмов, подходящих для любых больших ссылок O. Check @ KMan. –

Я боюсь, что вы недоразумение "Big-O" п otation.

Обозначение не выражено как алгоритм. Скорее, нота Big-O описывает свойство алгоритма.

Так что это не «O (N) может быть выражено как XXX», а скорее «алгоритм XXX имеет сложность O (N)».

При этом вполне резонно просить примеры алгоритмов с определенной сложностью; Вы уже перечисляете некоторые. Чтобы задать ваши вопросы:

~~O (4^n) - это то же, что и O (e^n), часто записываемое как O (exp (n)) (попробуйте понять, почему это то же самое).~~ O (4^n) относится к классу алгоритмов с «экспоненциальной сложностью» (EXPTIME). Многие важные проблемы в математике/CS имеют экспоненциальную сложность (или почти экспоненциальную сложность).

Алгоритм с экспоненциальной сложностью был бы, например, наивным решением для discrete logarithm problem.

Для других сложностей я не могу привести пример, но вы, вероятно, найдете его по ошибке.

источник

2010-10-25 08:35:28 sleske

Я не покупаю ваш O (a^n) = O (b^n) с a, b> 1. Хотя верно, что базис не имеет значения при работе с логарифмами, это не выполняется для экспоненциальных функций. В противном случае весь класс EXPTIME будет представлять собой набор задач с O (2^n) (или, более удобно, O ((1 + epsilon)^n)) алгоритмов. – bitmask

@bitmask: Собственно, это так. Википедия, например. определяет EXPTIME как «совокупность всех решений, решаемых детерминированной машиной Тьюринга в O (2^p (n)) времени» (при этом p (n) является многочленом от n). – sleske

BTW, мое первоначальное утверждение «O (4^n) совпадает с O (e^n)», конечно, ложно. То, что я имел в виду (но очень смутно), было то, что они оба в EXPTIME. Спасибо за напоминание :-). – sleske

-1

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

источник

2010-10-25 08:45:09

Если мы собираемся быть ничтожными. Любой алгоритм, который является 'Theta (f (N))', также * * O (f (N)) '. Таким образом, OP фактически прав, говоря, что они Big-O –

??? Это все как Big-O **, так и ** Omega, подразумевающие Theta. «это означает, что на некотором худшем вводе». Тета просто более конкретна, нижняя граница найдена и доказана. Это не связано с худшим случаем. «время работы всегда будет состоять в том, что« строго говоря, неверно, лучше было бы «рост ставки пропорционален Тэта». – Ishtar

Сложность времени Big-O

ответ

Смежные вопросы