Big O Notation

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

Bachmann–Landau notation

Paul Bachmann

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() -> ===

по 3 итераций внутри .split(), .reverse() и .join()
3 итерации при сравнении
два дополнительных массива и одна дополнительная строка

Итого: 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 символов

С двумя указателями:
N/2 итераций, 2 числа

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

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

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

O(1) - Константная
O(logN) - Логарифмическая
O(N) - Линейная
O(N*logN) - Линейно-логарифмическая
O(N^2) - Квадратичная
O(2^N) - Экспоненциальная
O(N!) - Факториальная

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

O(2N) -> O(N)

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

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

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

O(4N) -> O(N)

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

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

arr[index] - O(1)
arr.push(item) - O(1)
arr.pop() - O(1)
arr.shift/unshift - O(N)
arr.sort() - O(N*logN)
arr.forEach/find/indexOf - O(N)
document.querySelector(selector) - O(N)

map.set(key, value) - O(1)
map.delete(key) - O(1)
map.get/has(key) - O(1)
map.keys/values/entries - O(N)
set.add/delete/has(item) - O(1)
set.values/entries - O(N)
document.getElementById(id) - O(1)

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

O(N*M)

O(N+M)

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

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

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

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

Сomplexity 100%

@fireuppro

Big O Notation

Big O Notation

Bachmann–Landau notation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сomplexity 100%

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

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