Вычислительная и емкостная сложность алгоритма
Физическое время реализации алгоритма при некотором наборе входных данных может быть определено как
В зависимости от существующей на данной стадии разработки алгоритма его детализации аналогичной по смыслу с Временная и вычислительная сложность являются функцией от размера входа. Размер входа – скаляр, если количество, например, некоторых действий или шагов зависит только от одного параметра входа задачи. Например, в задачах на графах – только от количества вершин или рёбер. Размер входа – вектор, если от нескольких: для графов – количество вершин, рёбер, локальной степени вершин и т. д.
|
, где 
- количество операций i-ого типа, 
- время выполнения операции i-го типа, n – количество типов операций. Для одного и того же алгоритма при заданном наборе входных данных время t зависит от языка программирования и быстродействия конкретной ЭВМ. Если мы имеем такую оценку для нескольких алгоритмов решения одной и той же задачи, реализованных на разных языках и предназначенных для выполнения на ЭВМ с различным быстродействием, очевидно, что объективный выбор алгоритма выполнить невозможно. Можно принять за эталон некоторую операцию и, зная отношение времени выполнения i-й операции ко времени выполнения эталонной, можно определить суммарное число эталонных операций:
. Коэффициенты 
можно трактовать как относительное количество тактов 
. Объективная мера временной сложности алгоритма должна быть машинно- и программно-независимой. В качестве такой меры может выступать 
или 
.
, где 
- отношение количества тактов выполнения i-й операции к количеству тактов выполнения эталонной; 
- количество тактов выполнения алгоритма при заданном наборе входных данных.
