Трудоемкость программы (алгоритма) – это зависимость количества массовых операций (сравнения, обмены, сдвиги, повторения цикла и т.п.) от объема (размерностей) обрабатываемых данных.
Самое важное, что трудоемкость напрямую не связана со временем выполнения программы, но является мерой затрат на ее выполнение. Отметим наиболее важные свойства трудоемкости:
трудоемкость определяется отдельно для каждого вида операций;
трудоемкость может зависеть от входных данных. Поэтому оценка трудоемкости дается для лучшего и худшего случая, а также в среднем Tmin, Tmax, Tср . Свойство программы – иметь различную трудоемкость для разных данных, называетсячувствительностью к данным;
на практике обычно используется грубая оценка трудоемкости, основанная на понятии скорости (степени) роста функции.
