Большой класс O для (1/2) ^ n

К какому классу Big O относится функция (1/2)^n?

Чисто с математической точки зрения кажется, что нам придется поместить его в O (1), потому что 1/2 ^ n приближается к 0 для любого достаточно большого n.

Однако, когда дело доходит до асимптотического анализа и большого O, мы склонны много махать руками, а также возвращаться к формулам. 1/2 технически является константой, поэтому, казалось бы, попадет в O (c ^ n).

Я склоняюсь к O(c^n), потому что фраза «половина операции» не имеет смысла, когда речь идет об алгоритмах. Какой алгоритм занимает половину времени по мере увеличения входных данных? В лучшем случае я вижу математическую формулу (1/2)^n, относящуюся к половине некоторой постоянной времени, скажем, к минуте. Итак, (30 секунд)^n становится огромным числом, и функция явно принадлежит O(c^n).

Небольшая помощь?


algorithm big-o asymptotic-complexity
person zzu    schedule 02.10.2016    source источник
comment
Убывающие функции не так часто используются при анализе стоимости времени выполнения/пространства, но вы постоянно сталкиваетесь с ними при анализе количества числовых ошибок. Там действительно важна разница между 1 и 1/n и 1/2^n. Конечно, 1/n тривиально равно O(1), так как Big-O подобен ‹=. Может быть, вместо этого вы намеревались спросить о Big-Theta?   -  person Craig Gidney    schedule 03.10.2016
comment
Я пытаюсь разместить кучу математических функций в порядке от наименьшего порядка роста до самого высокого. Приведенная выше функция является одной из них. И я пытаюсь выяснить, принадлежит ли он, скажем, O (logn) или выше, скажем, O (n ^ 3).   -  person zzu    schedule 03.10.2016
comment
Итак, Big Theta работает... в каком классе Big Theta находится (1/2)^n?   -  person zzu    schedule 03.10.2016
comment
Не обязательно существует фиксированный набор больших классов, в которые попадает все, и многие функции лучше всего описываются сами по себе. Можете ли вы уточнить свой вопрос? Откуда это? Это проблемный вопрос?   -  person templatetypedef    schedule 03.10.2016
comment
Мне интересно, есть ли последовательный способ говорить об этом типе функции с точки зрения асимптотического анализа. Если нет, ок. Вы не можете говорить об отрицательном n с точки зрения алгоритмов (набор данных отрицательного размера не имеет смысла), так что, возможно, это то же самое. Мне интересно, учитывая общие пересечения между математикой и информатикой, установил ли кто-нибудь правило о том, как обращаться с этим типом функций.   -  person zzu    schedule 03.10.2016

Ответы (2)


arrow_upward
2
arrow_downward

Функция 0,5n равна O(1), а также O(c) для любого c > 0 (это не O(0), так как 0,5n > 0 для любого н).

Это также o(1) (примечание немного o). .

Это не (c) ни для какой константы c. Если c = 0, проблема в том, что 0,5n > c для любого n. Для любого c > 0 lim n0,5n ‹ c.

Лично я считаю, что утверждение (0,5n) является самым сильным и точным утверждением.

person Ami Tavory    schedule 03.10.2016
comment
Спасибо, @Am_I_Helpful! - person Ami Tavory; 03.10.2016

arrow_upward
0
arrow_downward

Вы не можете написать алгоритм O(1/2^N), потому что по мере приближения N к бесконечности время выполнения станет бесконечно малым, что физически невозможно. У вас не может быть меньше одной «операции».

person Malcolm McLean    schedule 02.10.2016
comment
Big-O не описывает исключительно временное поведение. - person ; 03.10.2016
comment
Я не согласен. Одним из основных применений Big-O является описание временной сложности. Я не думаю, что это редкость в информатике при сравнении алгоритмов? - person zzu; 03.10.2016
comment
@Malcolm McLean Я склонен с вами согласиться. Возможно, это не имеет смысла в контексте алгоритмов. Тем не менее, я решил проверить, есть ли уже какой-то консенсус относительно этого типа функций. Я знаю, что видел это в другом месте, но я никогда не видел, чтобы это обрабатывалось явно. - person zzu; 03.10.2016