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

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

Сравните это, скажем, с линейным временем (для некоторых входных данных 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^{n< /sup>). Тем не менее, он по-прежнему использует только простые сравнения, сложения и вызовы функций.}

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

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

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

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

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

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

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)

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

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

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

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

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

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

Рассмотрим факториал как контрпример. Факториал, скажем, 5 вычисляется как:

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

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

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

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

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

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

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

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

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