Для решения проблем нам нужны разные структуры данных. Например, двоичное дерево, LinkedList, массив, стек и т. д. Альтернативно, в одной и той же структуре данных, например массиве, мы можем использовать разные алгоритмы сортировки, такие как пузырьковая сортировка, сортировка вставками и т. д. Все эти варианты имеют последствия для качество, скорость, удобство использования и ресурсы, потребляемые нашим кодом. Поэтому очень важно знать, что мы пишем.
Omega представляет лучший случай, Theta — средний случай, а Omicron (Big O ) наихудший случай.Большая О всегда измеряет наихудший случай.
Предположим, у нас есть два фрагмента кода, и оба достигают одного и того же. Как нам решить, какой из них лучше? Big O – это способ математически понять это, помогая нам определить, какой код более эффективен.
Big O понимает это двояко:
- Временная сложность: масштабирование в зависимости от количества операций.
- Пространственная сложность: объем памяти, который что-то использует.
Сразу покажу на примере.
function logElements(n) { for(let i = 0; i < n; i++) { console.log(i) } } logElements(4)
Мы передали функции число n, и она выполнялась n раз. В примере мы прошли 10, и он запустился 10 раз. По этой причине результат равен O(n)
Есть несколько способов упростить Big O, и один из них — Отбросить константы. Давайте попробуем это на примере, который включает цикл for.
function logElements(n) { for(let i = 0; i < n; i++) { console.log(i) } for(let j = 0; j < n; j++) { console.log(j) } } logElements(4)
Вывод: 0, 1, 2, 3 для первого цикла и 0, 1, 2, 3 для второго цикла.
2н, 5н, 400н. Начальные константы не имеют значения. Если есть константа, мы ее отбрасываем, и результат становится O(n)
Давайте попробуем решить пример, который включает в себя цикл for внутри цикла for.
function logElements(n) { for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { console.log(i, j) } } } logElements(4)
Вывод начинается с 0 0, 1 1, … и останавливается, когда достигает 3 3.
Решение для большого О — n*n, поэтому это n2. Результат: O(n2).
Отбросить недоминирующие элементы – это еще один способ упростить Big O.
function logElements(n) { for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { console.log(i, j) } } for(let k = 0; k < n; k++) { console.log(k) } } logElements(4)
n2 здесь будет любым числом. Например, это будет 100000, поэтому n не может существенно повлиять на результат.
Давайте приведем несколько примеров с разными результатами.
function manyItems(n) { return n+n+n+n }
Будь то n+n+n+…+n или просто n+n, результат не изменится. Большой О — это О(1). O(1) представляет собой постоянное время.
На данный момент мы только коснулись основ; Подробнее я расскажу в своих следующих статьях. Я не все упомянул в этой статье, потому что некоторые темы сложны. Наконец, я включил сюда график эффективности Big O. До встречи в следующих статьях.