В чем разница между Θ (n) и O (n)?
4 ответа
Короткое объяснение:
, Если алгоритм имеет О (g (n)), это означает, что время выполнения алгоритма как n (входной размер) становится больше, пропорционально g (n).
, Если алгоритм имеет O (g (n)), это означает, что время выполнения алгоритма как n становится больше, самое большее пропорциональны g (n).
Обычно, даже когда люди говорят о O (g (n)) они на самом деле имеют в виду О (g (n)), но технически, существует различие.
<час>более технически:
O (n) представляет верхнюю границу. О (n) означает трудный связанный. О© (n) представляет нижнюю границу.
f (x) = О (g (x)) эквивалентность f (x) = O (g (x)) и f (x) = О© (g (x))
В основном, когда мы говорим, что алгоритм имеет O (n), это также O (n <глоток> 2 ), O (n <глоток> 1000000 ), O (2 <глоток> n )... но О (n) алгоритм не О (n <глоток> 2 ).
На самом деле, с тех пор f (n) = О (g (n)) средства для достаточно больших значений n, f (n) могут быть связаны в c1 г (n) и c2 г (n) для некоторых значений c1 и c2, т.е. темп роста f асимптотически равен g: g может быть нижней границей и и верхняя граница f. Это непосредственно подразумевает, что f может быть нижней границей и верхней границей g также. Следовательно,
f (x) = О (g (x)) эквивалентность g (x) = О (f (x))
Точно так же для показа f (n) = О (g (n)) достаточно показать, что g является верхней границей f (т.е. f (n) = O (g (n))), и f является нижней границей g (т.е. f (n) = О© (g (n)), который является той же самой вещью как g (n) = O (f (n))). Кратко,
<час>f (x) = О (g (x)) эквивалентность f (x) = O (g (x)) и g (x) = O (f (x))
существует также, мало-о, и мало-омега (ω) нотации, представляющие свободные верхние и свободные нижние границы функции.
Для суммирования:
f(x) = O(g(x))(большой об) означает, что темп ростаf(x)асимптотически меньше чем или равен [1 118] к темпу ростаg(x).
f(x) = Ω(g(x))(большая омега) означает, что темп ростаf(x)асимптотически больше, чем или равный [1 119] темп ростаg(x)
f(x) = o(g(x))(мало-о), средства, что темп ростаf(x)асимптотически меньше чем [1 120] темп ростаg(x).
f(x) = ω(g(x))(мало-омега) означает, что темп роста [1 111] асимптотически больше, чем [1 121], темп роста [1 112]
f(x) = Θ(g(x))(тета) означает, что темп роста [1 114] асимптотически равен [1 122] темп роста [1 115]
Для более детального обсуждения, Вы можете читать определение на Википедию или консультироваться с классическим учебником как Введение в Алгоритмы Cormen и др.
-
1@PeterRitchie - Параллельные проекты, устанавливающие, принимают значение по умолчанию количество доступных ядер, и я не попытался увеличить его до больше, но я уверен, что это не работало бы. Что касается того, если что я сказал в своем ответе, я просто попробовал это на решении с двумя проектами, переключение флажков на зависимостях действительно диктует, если они оба создают одновременно, или если они создаются последовательно. Даже если список заказов сборки был теми же обоими путями. – malexander 7 December 2013 в 06:31
каждый - Большой "O"
, каждый - Большая Тета
http://en.wikipedia.org/wiki/Big_O_notation
, Большой O означает, что Ваш алгоритм не выполнится на больше никаких шагов, чем в данном выражении (n^2)
, Большая Омега означает, что Ваш алгоритм не выполнится ни на каком меньшем количестве шагов, чем в данном выражении (n^2)
, Когда оба условия будут верны для того же выражения, можно использовать большую нотацию теты....
-
1Таким образом, когда я раскрываю число к 1, оно действительно создает. Все еще Пытаясь найти " пропавшие без вести dependency" но твердо с 21 проектом в решении. – lockwobr 7 December 2013 в 10:41
f(n) принадлежит O(n), если существует положительный k, поскольку f(n)<=k*n
f(n) принадлежит Θ(n), если существует положительный k1, k2 как k1*n<=f(n)<=k2*n
-
1Никакое преступление, но я не понял Ваше примечание редактирования. Это кажется неоднозначным мне. Будьте более конкретными так, чтобы я мог выручить Вас легко. – cafebabe1991 25 February 2014 в 13:33
Существует простой путь (прием, я предполагаю) помнить, который нотация означает что.
Все Нотации "большого О", как могут полагать, имеют панель.
При рассмотрении О©, панель внизу, таким образом, это - (асимптотическая) нижняя граница.
При рассмотрении О , панель находится, очевидно, в середине. Таким образом, это - (асимптотическое) связанное трудное.
, Когда почерк O, Вы обычно заканчиваете наверху и тянете загогулину. Поэтому O (n) является верхней границей функции. Честно говоря, этот не работает с большинством шрифтов, но это - исходное выравнивание имен.
-
1Возможно, я должен разъяснить свой ответ, но что я пытался передать, был то, что, если Вы на самом деле не устанавливаете флажок, что объект является зависимостью, проекты в списке заказов сборки могут создать параллельно и не последовательно. – malexander 7 December 2013 в 06:36