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

Question

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

---

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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.

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

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

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

public void doNothing(){}

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

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

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