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

Нет. Это O (c) по соглашению, если у вас нет зависимости от размера ввода, где c - любая положительная константа (обычно используется 1 - O (1) = O (12.37)).

Я бы сказал, что это 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) эквивалентен пустому алгоритму.

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

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

O (1) означает, что временная сложность алгоритма всегда постоянна.

Допустим, у нас есть такой алгоритм (на языке C):

void doSomething(int[] n)
{
  int x = n[0]; // This line is accessing an array position, so it is time consuming.
  int y = n[1]; // Same here.
  return x + y;
}

Я игнорирую тот факт, что массив может иметь менее 2 позиций, просто для простоты.

Если мы посчитаем две самые дорогие строки, общее время будет равно 2.

2 = O (1), потому что:

2 <= c * 1, если c = 2, для каждого n > 1

Если у нас есть этот код:

public void doNothing(){}

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

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

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

0 = O(f) для всех функций f, так как 0 <= |f|, поэтому это также O(0).

У меня есть очень простой аргумент в пользу того, что пустой алгоритм является 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)).

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

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

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

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

Но опять же, вот этот код O (0) :

// Hello world!

:)

Приведем формальное определение большого O:

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

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

|f(x)| <= M * |g(x)| для каждого 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) или что-то подобное.

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

Учтите:

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

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

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

В нескольких ответах говорится, что сложность 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).

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

Итак, для анализа временной сложности в терминах больших O вам нужна функция от n. Ваш алгоритм всегда делает аргументированно 0 шагов, но без изменяющегося параметра говорить об асимптотическом поведении бессмысленно. Предположим, что ваш алгоритм параметризован n. Только теперь вы можете использовать асимптотические обозначения. Бессмысленно говорить, что это 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) не означает константу, а означает ограниченность константой.