Big O Notation

@alexeycorr

Big O Notation

Сложность и как её определить

Bachmann–Landau notation

Paul Bachmann
Paul Bachmann
Edmund Landau
Edmund Landau

Палиндром: Однострочник

Однострочник: шаг 0

ЛОЛ

Однострочник: шаг 1

ЛОЛЛОЛ
.split()

Однострочник: шаг 2

ЛОЛЛОЛ
ЛОЛ
.split() -> .reverse()

Однострочник: шаг 3

ЛОЛЛОЛ
ЛОЛЛОЛ
.split() -> .reverse() -> .join()

Однострочник: шаг 4

ЛОЛЛОЛ
ЛОЛЛОЛ
.split() -> .reverse() -> .join() -> ===

Однострочник: шаг 4

ЛОЛЛОЛ
ЛОЛЛОЛ
.split() -> .reverse() -> .join() -> ===

Однострочник: шаг 4

ЛОЛЛОЛ
ЛОЛЛОЛ
.split() -> .reverse() -> .join() -> ===

Однострочник: выводы

.split() -> .reverse() -> .join() -> ===

Итого: 12 итераций и 9 дополнительных ячеек памяти.

Палиндром: С двумя указателями


Пример

С двумя указателями: шаг 0

ЛОЛ

С двумя указателями: шаг 1

ЛОЛ
0
2
start = 0; end = N - 1;

С двумя указателями: шаг 2

ЛОЛ
0
2
start = 0; end = N - 1; -> start < end

С двумя указателями: шаг 3

ЛОЛ
0
2
start = 0; end = N - 1; -> start < end -> str[start] === str[end]

С двумя указателями: выводы

start = 0; end = N - 1; -> start < end -> str[start] === str[end]

Итого: 1 итерация и 2 числа дополнительной памяти.

Посчитаем сложность

Однострочник:
4N итераций, 3N символов

Сложность алгоритма

Зависимость объёма работы, которая выполняется алгоритмом, от размера входных данных, выраженная математической функцией.

Варианты сложности

Отбрасывание констант

O(2N) -> O(N)

Отбрасывание констант

O(N * N^2) -> O(N^2)

Отбрасывание констант

O(4N) -> O(N)

O(N/2) -> O(N)

Встроенные методы

Потренируемся


O(N*M)

Палиндром, тест скорости

Сортировка, тест скорости

Память тоже важна

В любой непонятной ситуации копируй данные!
const copyData = [...data]; -> O(N)

Сomplexity 100%

@fireuppro

Спасибо за внимание!

Подписывайтесь, ставьте лайки!

Linkedin GitHub Instagram Telegram @alexeycorr