Постоянное время фактически означает, что вы можете задать постоянную верхнюю границу для продолжительности выполнения программы, на которую не влияет ни один из входных параметров.
Сравните это, скажем, с линейным временем (для некоторого ввода 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) ). Хотя он все еще использует только простые сравнения, сложения и вызовы функций.