Fundamentos

Um algoritmo é uma sequência finita de passos bem definidos que, dada uma entrada válida, produz uma saída e termina. Cada passo é executável, e a execução para.

Correção, custo f(n) e as famílias de projeto deste tópico — e heapsort, quicksort e guloso nos seguintes — partem dessa sequência e da conta de operações.

As páginas se agrupam em cinco blocos. O primeiro fixa o que conta como algoritmo e classifica o projeto em cinco famílias.

O segundo ordena no próprio vetor e lê o custo da entrada já ordenada, da invertida e da típica.

O terceiro compara o formato de duas funções de custo quando n cresce.

O quarto descreve a chamada que se invoca e o esquema que parte, resolve e combina, com T(n) na árvore e no Teorema Mestre.

O quinto interpreta o infixo numérico no pseudocódigo e extrai fatores de várias variáveis na mesma volta.

Uma chamada por passo, ou duas ou mais, e o tempo e o espaço do Fibonacci com duas chamadas estão em Recursão. Intercalar duas metades e aplicar o Teorema Mestre a T(n) = 2T(n/2)+cn estão em Dividir para Conquistar.

Crescimento de Funções classifica f = O(g), f = o(g), f = Ω(g) e f = Θ(g), e compara 2ⁿ com n!. Resolver a recorrência de metades está em Dividir para Conquistar.

Primeiros Passos ordena no próprio vetor por comparações e deslocamentos. Dividir para Conquistar parte em duas fatias, ordena cada uma e intercala.

a∧b = aᵇ e N = 2ⁱ no pseudocódigo estão em Operadores de Pseudocódigo. O laço que multiplica resp por i e divide cada variável ainda divisível, sem avançar i, está em MDC e MMC.