Grande O Notação em JavaScript
Big O Notation, colectivamente chamada notação Bachmann-Landau ou notação assimptótica, é uma forma de descrever o desempenho de um algoritmo. É utilizada para descrever o pior cenário possível de um algoritmo. É utilizada para comparar o desempenho de diferentes algoritmos. Descreve a implementação de um algoritmo em termos do tamanho da entrada.
A notação Big O caracteriza funções de acordo com as suas taxas de crescimento: tarefas com a mesma taxa de crescimento são consideradas como sendo da mesma ordem. É uma notação matemática que descreve o comportamento limitador de uma função quando o argumento tende para um determinado valor ou infinito. É utilizada para classificar os algoritmos de acordo com a forma como o seu tempo de execução ou as suas necessidades de espaço crescem à medida que o tamanho da entrada aumenta. A letra O é utilizada porque a taxa de crescimento de uma função é também chamada a sua ordem.
Iteration
For loop
for (let i = 0; i < n; i++) {
console.log(i)
}
O código acima será executado n vezes. A complexidade temporal deste código é O(n).
While loop
let i = 0
while (i < n) {
console.log(i)
i++
}
O código acima será executado n vezes. A complexidade temporal deste código é O(n).
Do while loop
let i = 0
do {
console.log(i)
i++
} while (i < n)
O código acima será executado n vezes. A complexidade temporal deste código é O(n).
Recursion
Factorial
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
O código acima será executado n vezes. A complexidade temporal deste código é O(n).
Fibonacci
function fibonacci(n) {
if (n <= 1) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
O código acima será executado n vezes. A complexidade temporal deste código é O(n).
Searching
Linear Search
function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i
}
}
return -1
}
O código acima será executado n vezes. A complexidade temporal deste código é O(n).
Binary Search
function binarySearch(arr, value) {
let start = 0
let end = arr.length - 1
let middle = Math.floor((start + end) / 2)
while (arr[middle] !== value && start <= end) {
if (value < arr[middle]) {
end = middle - 1
} else {
start = middle + 1
}
middle = Math.floor((start + end) / 2)
}
if (arr[middle] === value) {
return middle
}
return -1
}
O código acima correrá log(n) vezes. A complexidade temporal deste código é O(log(n)).
Sorting
Bubble sort
function bubbleSort(arr) {
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
O código acima será executado n^2 vezes. A complexidade temporal deste código é O(n^2).
Selection sort
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j
}
}
if (i !== lowest) {
let temp = arr[i]
arr[i] = arr[lowest]
arr[lowest] = temp
}
}
return arr
}
O código acima será executado n^2 vezes. A complexidade temporal deste código é O(n^2).
Insertion sort
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i]
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j]
}
arr[j + 1] = currentVal
}
return arr
}
O código acima será executado n^2 vezes. A complexidade temporal deste código é O(n^2).
Merge sort
function mergeSort(arr) {
if (arr.length <= 1) return arr
let mid = Math.floor(arr.length / 2)
let left = mergeSort(arr.slice(0, mid))
let right = mergeSort(arr.slice(mid))
return merge(left, right)
}
function merge(left, right) {
let results = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
results.push(left[i])
i++
} else {
results.push(right[j])
j++
}
}
while (i < left.length) {
results.push(left[i])
i++
}
while (j < right.length) {
results.push(right[j])
j++
}
return results
}
O código acima será executado n log(n) vezes. A complexidade temporal deste código é O(n log(n)).
Quick sort
function pivot(arr, start = 0, end = arr.length + 1) {
let pivot = arr[start]
let swapIdx = start
function swap(array, i, j) {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
for (let i = start + 1; i < arr.length; i++) {
if (pivot > arr[i]) {
swapIdx++
swap(arr, swapIdx, i)
}
}
swap(arr, start, swapIdx)
return swapIdx
}
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
let pivotIndex = pivot(arr, left, right)
quickSort(arr, left, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, right)
}
return arr
}
O código acima será executado n log(n) vezes. A complexidade temporal deste código é O(n log(n)).
Dicas para o Big O
- As operações aritméticas são constantes
- A atribuição de variáveis é constante
- O acesso aos elementos de uma matriz (por índice) ou objecto (por chave) é constante
- Num loop, a complexidade é a duração do loop vezes a complexidade do que quer que aconteça dentro do loop