#compsci 

**Вычислительная сложность** (computational complexity) - зависимость объёма работа от размера входных данных

Проблема: иногда число операций зависит еще от значений данных, например, сортировка уже упорядоченного набора чисел быстрее.
Поэтому два варианта изучения числа операций: в среднем случае, когда оно усредняется по ансамблю всех возможных входных параметров, и в худшем случае, когда оно изучается для такого набора данных, с которым [[алгоритм]] будет работать дольше всего

Рассматривается асимптотическое поведение зависимости объема работы от размера входных данных.

![[Pasted image 20260224002837.png]]

В информатике вычислительная сложность O(g(x)) понимается в смысле $\LARGE \Theta(g(x))$

>[!Примеры]
>Алгоритм сортировки слияниями - вычислительная сложность $\LARGE O(N \log{N})$ в худшем случае
>Алгоритм пузырьковой сортировки - $\LARGE O(N^2)$ в худшем случае

(основание логарифма не ставится, так как не имеет смысла под знаком асимптотики)

![[Pasted image 20260224003137.png]]

Стоит помнить, что определение вычислительной сложности для $\LARGE N \rightarrow \infty$, поэтому лучшая асимптотика нее всегда означает лучший алгоритм

Пример: перемножение двух квадратных [[Matrix|матриц]] размера $\LARGE N$
![[Pasted image 20260224003432.png]]

## Улучшение алгоритмов
Можно ли придумать новый алгоритм, который будет лучше старых в смысле асимптотической вычислительной сложности?
Для некоторых задач есть ответ на этот вопрос в виде соответствующих теорем

Например:
![[Pasted image 20260224003825.png]]
![[Pasted image 20260224004005.png]]