Алгоритмы (курс Тинькофф)

Асимптотический анализ

Используется для оценки алгоритмов. Оценивается не то сколько алгоритм работает на конкретных данных, а то сколько алгоритм работает в зависимости от размера входа (объема данных).

T(n) - сколько времени работает алгоритм на входе какого-то размера n.

В чем измерить сколько работает программа?

Нужно посчитать количество действий которые выполняет программа, колисество read/write операций.

RAM(Random Access Memory) - модель

Имеет следующие правила:

• К любой ячейке памяти можно за O(1) обратиться(read) и за O(1) записать что-то(write).

Базовыми операциями, которыми можно вычислять скорость - это опреации read, write.

$O(n)$ - обозначает такую скорость которая при увеличении размера входных данных начиная с какого то момента будет ниже, чем график функции, которая ее определяет - оценка сверху. (условно худшая скорость)

$\Omega(n)$ - оценка снизу - обозначает такую скорость которая при увеличении размера входных данных начиная с какого то момента будет выше, чем график функции, которая ее определяет - оценка снизу.

$\Theta(n)$ - если одновременно выполняются условия $O(n)$ и $\Omega(n)$