Big O обозначение для обратного экспоненциального алгоритма

Question

Допустим, у вас был алгоритм, который имел сложность n ^ (- 1/2), скажем, научный алгоритм, в котором один образец не дает большого количества информации, поэтому для его обработки требуется много времени, но было сделано много примеров для перекрестных ссылок. это быстрее. Вы бы представили это как O (n ^ (- 1/2))? Это вообще возможно теоретически? Tldr вы можете иметь обратную экспоненциальную сложность времени?

Answer 1

Вы можете определить O (n ^ (- 0,5)), используя этот набор:

O (n ^ (- 0,5)): = {g (n): существуют положительные постоянные c и N, такиечто 0 <= g (n) <= cn ^ (- 0,5) для n> N}.

Функция n ^ (- 1), например, принадлежит этому набору.

Однако ни один из элементов из вышеперечисленного не может быть верхней границей времени работы алгоритма.

Обратите внимание, что для любой константы c:

если: n> c ^ 2, тогда: n ^ (- 0,5) * c <1. </p>

Это означает, что ваш алгоритмсделать менее одной простой операции для ввода достаточно большой. Поскольку он должен выполнять натуральное число простых операций, мы имеем, что он выполняет ровно 0 операций - вообще ничего.

Answer 2

Уменьшение времени работы на практике не имеет смысла (даже меньше, если оно уменьшается до нуля). Если бы это существовало, вы бы нашли способы добавления фиктивных элементов и искусственного увеличения N.

Но большинство алгоритмов имеют как минимум сложность O (N) (всякий раз, когда каждый элемент данных влияет на окончательное решение);даже если нет, просто представление N становится длиннее и длиннее, что в конечном итоге увеличивает время работы (например, O (Log N)).