ВПЕРЁД ⇒
⇐ НАЗАД
Время работы алгоритма
Важной характеристикой алгоритма является время его работы (сложность по времени, временнАя сложность, сложность вычислений, time complexity).
Время работы, несмотря на своё название, отображает не столько само значение времени, сколько количество выполняемых компьютером логических (программных) операций. Причина кроется в том, что различные компьютеры (например, обладающие процессорами с одинаковыми наборами аппаратных инструкций, но различающимися тактовыми частотами), будут выполнять один и тот же алгоритм за различное время (хотя при этом количество логических операций, выполненных разными компьютерами, может совпадать). С другой стороны, алгоритм может выполняться на процессорах с одинаковыми тактовыми частотами, но отличающимися наборами инструкций. В этом случае, выполнение одной и той же логической операции может приводить в процессорах (с различающимися наборами инструкций) к использованию различного количества аппаратных инструкций. Таким образом, время выполнения одной логической операции различными процессорами в общем случае будет отличаться, то есть само значение времени работы - вещь непостоянная, которая может изменяться даже при повторных запусках программы на одном и том же компьютере.
Для одного и того же компьютера время работы алгоритма может варьироваться по причине множества факторов, вот некоторые из них:
- насколько качественно в коде был реализован алгоритм (один и тот же алгоритм на одном и том же языке программирования разные программисты могут реализовывать по-разному);
- на каком языке программирования реализован алгоритм (компиляторы разных языков будут генерировать разное количество процессорных инструкций);
- какой уровень оптимизации генерации бинарного кода был выставлен компилятору при сборке программы.
Несмотря на то, что под временем работы подразумевается не длительность исполнения программы, реализующей алгоритм, а количество логических операций, затрачиваемых компьютером на исполнение программы, можно утверждать, что выполнение минимизации количества логических операций, используемых в алгоритме, также ведёт к минимизации времени исполнения алгоритма. Если сделать упрощение и представить, что все виды операций выполняются одним и тем же компьютером за одно и то же время, то получим, что линейное увеличение/уменьшение количества логических операций в алгоритме будет приводить к линейному увеличению/уменьшению длительности исполнения программы, реализующей алгоритм.
ВПЕРЁД ⇒
⇐ НАЗАД
Источники
Категория
Теги