Что означает "в постоянное время"?

Ответ 1

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

Сравните это, например, с линейным временем (для некоторого ввода n), который часто будет фактически размером входных данных, а не прямым значением), что означает, что верхняя граница времени может быть выражена как mn + k для некоторых значений m и k.

Обратите внимание, что это не означает, что программа будет принимать одинаковое количество времени для любых входных данных только потому, что она работает в постоянное время. Например, рассмотрим этот метод:

int foo(int n)
{
    if (n == 0)
    {
        return 0;
    }
    int j = n + 1;
    int k = j * 2;
    return k;
}

Это делает больше работы в случае, когда n отличен от нуля, чем в случае, когда он равен нулю. Тем не менее, это все еще постоянное время - самое большее, это будет делать одно сравнение, одно добавление и одно умножение.

Сравним это с рекурсивной функцией:

public int foo(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n * foo(n - 1);
}

Это будет возвращать n раз - поэтому оно линейно в n. Однако вы можете стать намного хуже линейного. Рассмотрим этот метод вычисления числа Фибоначчи:

public int fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    return fib(n - 2) + fib(n - 1);
}

Это не выглядит намного хуже предыдущей версии, но теперь это экспоненциально (верхняя граница наиболее легко выражается в терминах O (2 ⁿ). Она по-прежнему использует только простые сравнения, добавление и вызов функций.

Ответ 2

"Постоянное время" означает, что операция будет выполняться в течение некоторого времени (или пространства памяти - это часто измеряемая вещь) независимый от размера ввода. Обычно вы выбираете переменную (используйте n), чтобы указать размер ввода.

O(1) - постоянное время - время работы не зависит от n

O(n) - линейное время - время работы линейно пропорционально n

O(n^2) - квадратичное время - время работы пропорционально квадрату n

Это всего лишь несколько примеров; возможности безграничны. См. Статью wiki в complexity

Вот несколько конкретных способов, которыми программа, состоящая только из перечисленных вами операций, может занимать различные промежутки времени:

int n = // some value
doSomething
doSomething
doSomething

Обратите внимание, что это три значения длины, независимо от того, что n. O(1)

int n = // some value
def f(n):
    if n == 0 return
    doSomething
    f(n-1)
f(n)

Теперь мы запускаем что-то для каждого значения 0..n(линейное время, O(n))

И мы можем немного повеселиться -

int n = //some value
def f(n):
    if n == 0 return
    doSomething
    f(n-1)
    f(n-1)

Какое время работы здесь? (т.е. сколько вещей мы выполняем?):)

Ответ 3

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

Ответ 4

В "постоянном времени" обычно означает, что время, затрачиваемое на вычисление результата, не зависит от размера ввода.

Например. Вычисление длины списка/вектора на большинстве управляемых языков выполняется в постоянное время независимо от того, насколько велик список. Размер сохраняется как отдельное поле и обновляется по мере того, как список растет и сжимается. Но вычисление счета так же просто, как чтение поля.

Вычисление размера двусвязного списка очень часто не является постоянным. Список часто может быть изменен с обоих концов, и, следовательно, нет центрального места для хранения счета. Следовательно, определение длины списка требует посещения и определения количества элементов. Так как список растет, так это время, необходимое для вычисления ответа.

Ответ 5

Постоянное время здесь означает не зависящее от количества входов (а не самого входа), и если вам не разрешено или недоступно, единственный способ сделать это зависит от количества входов - это условия и рекурсия. Хотя вы можете утверждать, что рекурсия не нужна с некоторыми спорными решениями. Например. (в C)

if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();
if(ReadInput()) DoSomeThing();

Ответ 6

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

Ответ 7

Если программа работает вечно, она не завершается за определенное количество времени, потому что она не завершена. Мы применяем понятие "постоянное время" к прогону всей программы, а не к каждому отдельному этапу.

"постоянное время" означает "время, не зависящее от количества ввода".

Ответ 8

"В постоянном времени" означает, что независимо от того, что представляет собой вход, программа не будет работать дольше известного времени.

Рассмотрим факторную функцию как контрпример. Факториал, скажем, 5, вычисляется следующим образом:

5! = 5 * 4 * 3 * 2 * 1 = 120

Это, очевидно, займет меньше времени для вычисления, чем факториал 10, потому что для выполнения последнего программа должна выполнить еще пять умножений:

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Итак, "постоянное время" не означает, что мы знаем, как долго программа будет работать в каждом случае, но что она никогда не будет работать дольше, чем известное количество времени (верхняя граница).