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

Question

Я изучаю алгоритм, но я не понимаю алгоритм постоянного времени.

Что это значит и как отличается с алгоритмами линейного времени.

Спасибо,

Answer 1

Постоянное время просто означает, что независимо от размера ввода функции функция всегда остается неизменной.

Вот простой пример, представьте, у вас есть функция под названием deleteHead, который когда данный узел в связанном списке, возвращает следующий:

function deleteHead(list) { 
    if(list == null) 
     return null; 
    return list.next; 
} 

Независимо от размера списка, вы даете это функция (десять элементов или миллиард из них), она всегда делает только одну вещь, которая делает ее постоянным алгоритмом времени O (1).

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

Answer 2

При изменении размера входного сигнала для алгоритма с постоянной времени, среда выполнения не будет расти.

См., Например, линейные алгоритмы, при изменении размера ввода, время выполнения растет (линейно).

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

Примеров см Wikipedia: Time complexity

Answer 3

Для алгоритмов постоянная времени, время выполнения не зависит от размера входных данных. Для линейного времени время выполнения линейно увеличивается с размером ввода.

Answer 4

Это находится в большинстве основных книг по компьютерной науке.

Он просто описывает зависимость между входной длиной алгоритма или размера объекта (в зависимости от приложения) и времени, которое требуется выполнить. НАПРИМЕР. при использовании списка требуется постоянное количество шагов для добавления объекта спереди/сзади, независимо от того, насколько велик список.

Линейное время требуется для поиска определенного элемента в списке (в худшем и среднем случае) - если у вас есть список в два раза длиннее, вам придется искать в два раза больше предметов, чтобы найти тот, который вы