Является ли временная сложность пустого алгоритма O (0)?

Question

Итак, с учетом следующей программы:

---

Является ли временная сложность этой программы O (0)? Другими словами, 0 0 (0)?

Я думал, что ответ на этот вопрос в отдельном вопросе пролил бы свет на этот вопрос .

РЕДАКТИРОВАТЬ: Здесь много хороших ответов! Мы все согласны с тем, что 0 есть O (1). Вопрос в том, 0 0 (0) также?

Answer 1

Требуется одинаковое количество времени для запуска независимо от входа, поэтому по определению это O (1).

Answer 2

Из Википедия :

Описание функции в терминах большой буквы O обычно дает только верхнюю границу скорости роста функции.

Из этого описания, поскольку для выполнения пустого алгоритма требуется 0 раз, он имеет верхнюю границу производительности O (0). Это означает, что это также O (1), который оказывается большей верхней границей.

Редактировать

Более формально из CLR (1ed, стр. 26):

Для данной функции g ( n ) мы обозначаем O ( g ( n *) 1027 *)) набор функций

O ( g ( n )) = { f ( n ): существуют положительные константы c и n ₀ такие, что 0 & le; f (n) & le; cg ( n ) для всех n & ge; n ₀ }

Асимптотическое время выполнения пустого алгоритма, выполняемого за 0 раз независимо от входных данных, поэтому является членом O (0).

Редактировать 2 :

Мы все согласны с тем, что 0 - это O (1). Вопрос в том, 0 0 (0) также?

На основании определений я говорю да.

Кроме того, я думаю, что этот вопрос немного важнее, чем указывают многие ответы. Сам по себе пустой алгоритм, вероятно, не имеет смысла. Однако всякий раз, когда указывается нетривиальный алгоритм, пустой алгоритм можно рассматривать как лежащий между последовательными этапами заданного алгоритма, а также до и после шагов алгоритма. Приятно осознавать, что «ничто» не влияет на асимптотическое время алгоритма.

Редактировать 3 :

Адам Крум предъявляет претензию :

Для любой функции f ( x ), f ( x ) в O ( f ) ( х * * тысяча девяносто четыре)).

Доказательство: пусть S будет подмножеством R и T будет подмножеством R ^* (неотрицательные действительные числа) и пусть f ( x ): S -> T и c & ge; 1. Тогда 0 & le; f ( x ) & le; f ( x ), что приводит к 0 & le; f ( x ) & le; ср ( x ) для всех x∈ S . Поэтому f ( x ) ∈ O ( f ( x )).

В частности, если f ( x ) = 0, то f ( x ) ∈ O (0).

Answer 3

У меня есть очень простой аргумент для пустого алгоритма: O (0): для любой функции f (x) f (x) находится в O (f (x)). Просто пусть f (x) = 0, и мы имеем 0 (время выполнения пустого алгоритма) в O (0).

Кстати, я ненавижу, когда люди пишут f (x) = O (g (x)), когда должно быть f (x) ∈ O (g (x)).

Answer 4

В нескольких ответах говорится, что сложность равна O (1), поскольку время является константой, а время ограничено произведением некоторого коэффициента и 1. Что ж, верно, что время является константой, и оно ограниченоКстати, но это не значит, что лучшим ответом будет O (1).

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

Пустой алгоритм находится в O (n ^ 2) и в O (n) и в O (1) и в O(0).Я голосую за O (0).

Answer 5

Big O - асимптотическая запись.Чтобы использовать большой O, вам нужна функция - другими словами, выражение должно быть параметризовано с помощью n, даже если n не используется.Нет смысла говорить, что число 5 - это O (n), а постоянная функция f (n) = 5 - это O (n).

Итак, для анализа сложности времени с точки зрения больших Oвам нужна функция n.Ваш алгоритм всегда делает возможно 0 шагов, но без переменного параметра говорить об асимптотическом поведении не имеет смысла.Предположим, что ваш алгоритм параметризован.Только теперь вы можете использовать асимптотику.Нет смысла говорить, что это O (n ² ) или даже O (1), если вы не укажете, что такое n (или переменная, скрытая в O (1))!

Как только вы определитесь с числом шагов, вопрос определения большого O будет определяться следующим образом: функция f (n) = 0 равна O (0).

Поскольку этоНизкоуровневый вопрос зависит от модели расчета.При «идеалистических» предположениях возможно, что вы ничего не делаете.Но в Python вы не можете сказать def f(x):, а только def f(x): pass.Если вы предполагаете, что каждая инструкция, даже pass (NOP), занимает время, то сложность равна f (n) = c для некоторой константы c, и если только c != 0, вы можете только сказать, что f - это O (1).), а не O (0).

Стоит отметить, что большой O сам по себе не имеет ничего общего с алгоритмами.Например, вы можете сказать sin x = x + O (x ³ ) при обсуждении расширения Тейлора.Кроме того, O (1) не означает постоянную, а означает ограниченную постоянной.

Answer 6

Все ответы до сих пор обращаются к вопросу, как будто есть правильный и неправильный ответ.Но нет.Вопрос является вопросом определения.Обычно в теории сложности стоимость времени является целым числом - хотя это тоже всего лишь определение.Вы можете сказать, что пустой алгоритм, который выходит немедленно, занимает 0 шагов или 1 шаг.Это абстрактный вопрос, потому что сложность времени - это абстрактное определение.В реальном мире у вас даже нет временных шагов, у вас есть непрерывное физическое время;это может быть правдой, что один ЦП имеет тактовые циклы, но параллельный компьютер может легко иметь асинхронные тактовые частоты, и в любом случае тактовый цикл очень мал.

Тем не менее, я бы сказал, что более разумно сказать, чтооперация остановки занимает 1 временной шаг, а не 0 временных.Это кажется более реалистичным.Во многих ситуациях это, возможно, очень консервативно, потому что издержки инициализации обычно намного больше, чем выполнение одной арифметической или логической операции.Задание пустого алгоритма с 0 временными шагами было бы разумно только моделировать, например, вызовом функции, который удаляется оптимизирующим компилятором, который знает, что функция ничего не сделает.

Answer 7

С учетом формального определения Big O:

Пусть f (x) и g (x) две функции, определенные на множестве действительных чисел. Затем пишем:

f(x) = O(g(x)) по мере приближения x к бесконечности, если существует реальное M и реальное x0, так что:

|f(x)| <= M * |g(x)| for every x > x0

На мой взгляд, если подставить g (x) = 0 (чтобы иметь программу со сложностью O (0)), мы должны иметь:

|f(x)| <= 0, для каждого x> x0 (ограничение существования вещественных M и x0 здесь практически снято)

, которая может быть истинной, только когда f (x) = 0.

Так что я бы сказал, что не только пустая программа - это O (0), но и единственная, для которой это верно. Интуитивно понятно, что это должно было быть правдой, поскольку O (1) охватывает все алгоритмы, которые требуют постоянного числа шагов, независимо от размера его задачи, включая 0. Говорить об O (0) практически бесполезно; это уже в O (1). Я подозреваю, что это просто из-за простоты определения, что мы используем O(1), где это также может быть O(c) или что-то подобное.

Answer 8

Я бы сказал, что это O (1) по определению, но O (0), если вы хотите получить техническую информацию об этом: так как O (k ₁ g (n)) эквивалентно O (k) ₂ g (n)) для любых констант k ₁ и k ₂ , следовательно, O (1 * 1) эквивалентно O (0 * 1) ) и, следовательно, O (0) эквивалентно O (1).

Однако , пустой алгоритм не похож, например, на функцию тождества, определение которой является чем-то вроде «вернуть ваш ввод». Пустой алгоритм больше похож на пустой оператор, или что-то, что происходит между двумя операторами. Его определение «абсолютно ничего не делать с вашим вводом», по-видимому, даже без подразумеваемых накладных расходов, связанных с простым вводом.

Следовательно, сложность пустого алгоритма уникальна в том смысле, что O (0) имеет сложность, равную нулю, в зависимости от того, какая функция вам нравится, или просто ноль. Отсюда следует, что, поскольку весь бизнес настолько дурацкий, и так как O (0) уже не означает что-то полезное, и так как немного нелепо даже обсуждать такие вещи, разумно специальный случай для O (0) выглядит примерно так:

Сложность пустого алгоритма составляет O (0) во времени и пространстве. Алгоритм с временной сложностью O (0) эквивалентен пустому алгоритму.

Итак, поехали.

Answer 9

Нет такой вещи как O(0). Даже оракулу или гиперкомпьютеру требуется время для одной операции, т.е. solve(the_goldbach_conjecture), ergo:

Все машины, теоретические или реальные, конечные или бесконечные производят алгоритмы с минимальной временной сложностью O(1).

Но опять же, этот код прямо здесь O(0):

// Hello world!

:)

Answer 10

Должно быть O (1). Коэффициент всегда равен 1.

Рассмотрим:

Если что-то растет как 5n, вы не говорите O (5n), вы говорите O (n) [другими словами, O (1n)]

Если что-то растет, как 7n ^ 2, вы не говорите O (7n ^ 2), вы говорите O (n ^ 2) [другими словами, O (1n ^ 2)]

Точно так же вы должны сказать O (1), а не O (некоторая другая константа)