Eficiência de algoritmos: tempo e espaço

Conceitos em Ciência da Computação

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Introdução à notação Big-O

Mede o crescimento de tempo e espaço conforme a entrada aumenta
Exemplos: $O(n)$, $O(n^2)$, $O(\log\, n)$
"O" indica a ordem de crescimento, ex.: O(n) = linear

Complexidade de tempo - analogia de escritório

Um gráfico que mostra várias complexidades da notação Big O

$O(1)$ - tempo constante - "Olhar rápido" - "constante"
$O(\log\,n)$ - aumento lento - "Dividir pilha" - "logarítmica"
$O(n)$ - aumento linear - "Ler documento" - "linear"
$O(n\,\log\,n)$ - aumento mais rápido - "Ordenar pilha" - "linearítmica"
$O(n^2)$ - aumento quadrático - "Comparar documentos" - "quadrática"

Complexidade de espaço - analogia de escritório

Um gráfico que mostra várias complexidades da notação Big O

$O(1)$ - espaço constante - "Espaço na mesa" - "constante"
$O(\log\,n)$ - aumento lento de espaço - "Notas mínimas" - "logarítmica"
$O(n)$ - aumento linear - "Post-its" - "linear"
$O(n\,\log\,n)$ - aumento mais rápido - "Pilhas temporárias" - "linearítmica"
$O(n^2)$ - aumento quadrático - "Grade de comparação" - "quadrática"

Vamos praticar!

Conceitos em Ciência da Computação

Preparing Video For Download...