Эффективность

«О» большое (Big O notation) — это математическая нотация, которая позволяет оценить, как изменяется время выполнения алгоритма или объем используемой памяти в зависимости от размера входных данных. Есть еще «о» малое — эта нотация дает более строгую верхнюю границу для сложности алгоритма, но часто ее труднее вычислить, чем «О» большое. На практике «О» большое используется чаще, поскольку эта концепция проще для анализа и дает достаточно хорошую оценку сложности в большинстве случаев.

Биг О введено для оценки эффективности алгоритмов:

• Временная сложность - количество операций: которые должен выполнить алгоритм. Она показывает, как растет время выполнения алгоритма при увеличении входных данных.
• Пространственная сложность - измеряет объем памяти, которую он использует в зависимости от размера входных данных. На пространственную сложность влияют количество переменных, тип и размер структуры данных, вызовы функций и способ выделения памяти.

Биг О имеет три главных правила вычисления:

• Определение худшего случая
• Исключение постоянных величин
• Игнорирование всех процессов, которые вычисляются быстрее, чем самая медленная и тяжёлая часть алгоритма

При анализе выделяют три случая: лучший, средний и худший.

• Лучший - показывает, как быстро алгоритм выполняется для определённого входного значения. Имеет зависимость О(1).
• Средний - представляет собой прогноз о времени выполнения алгоритма, когда входные данные являются случайными. Зависимость О(n/2).
• Худший - означает, как долго алгоритм может выполниться для предоставленного входного значения. Зависимость O(n).