Вычислительная сложность хорошего алгоритма отличается от плохой тем, что она должна быть более эффективной для всех входных данных, за исключением, возможно, данных малого размера. 23

Для определения эффективности используют асимптотическую сложность. 12 Для её оценки оценивают скорость или порядок роста времени выполнения алгоритма при увеличении размера подаваемых на вход данных. 1 Алгоритм с меньшей асимптотической сложностью считается более эффективным. 23

По своей вычислительной сложности все алгоритмы подразделяются на несколько классов: 1

• Линейный. 1 Класс алгоритмов с временной сложностью, выражаемой линейной функцией от размера задачи. 1
• Полиномиальный. 1 Класс алгоритмов, временная сложность которых задаётся полиномиальной функцией, зависящей от размера задачи. 1
• Экспоненциальный. 1 Класс алгоритмов с временной сложностью, которая задаётся экспоненциальной функцией от размера задачи. 1

При этом полиномиальные алгоритмы считаются наиболее эффективными. 1 Примерами полиномиальных алгоритмов являются стандартные алгоритмы целочисленного сложения, умножения, деления, нахождения НОД, перемножения матриц, сортировки массивов, поиска данных и некоторые другие алгоритмы. 1