Ω(Х) – область задачи, где скорость роста их сложностей ниже чем скоротсь роста мощностей.О(Х)-скорость равна.θ(Х)-не успевает,скорость мощностей ниже скорости роста сложности. Наши мощности растут с ростом сложности.
Для оценки сложности алгоритмов существует много критериев. Чаще всего сложность алгоритма – количество необходимых для решения задачи ресурсов как функция от ее размера.
1. Временная сложность алгоритма – «время» выполнения алгоритма, измеряемое в «шагах» (инструкциях алгоритма, которые необходимо выполнить для достижения результата)
2. Емкостная сложность алгоритма – необходимый для работы алгоритма объём памяти машины.
3. Схемная сложность алгоритма – минимальный размер схемы из функциональных элементов, вычисляющей заданную (булеву) функцию .
