Regra do Produto: “Multiplicar Big-OS”
A regra produto simplifica o estado de como o Big-Os pode ser multiplicado.
Se f(n) é O(h(n)) e g(n) é O(p(n)), então f(n)g(n) é O(h(n)p(n)).
A seguir o bloco de código demonstra uma função com dois laços de for aninhado o qual a regra produto está aplicada:
Nesse exemplo, f(n) = 5n*n porque na linha 7 executa 5n vezes para um total de n interações. Além disso, isso resulta em um total de 5n^2 operações. Aplicando a regra do coeficiente, o resultado é O(n)= n^2.
Regra do Polinomial: “Big-OS para o Poder do K”
A regra de estado do polinomial tem as complexidades de tempo.
Se f(n) é um polinomial de grau k, então f(n) é O(n^k).
A seguir o bloco do código tem apenas um laço de loop de complexidade de tempo quadrático:
Nesse exemplo, f(n) = n^2 porque a linha 4 executa interações n*n.
Fonte: JavaScript Data Structures and Algorithms: An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals (English Edition)
Deixe um comentário