Algoritmos e complexidade Flashcards
O que são sub-rotinas?
São blocos (de funções) que realizam tarefas específicas
Para o que sub-rotinas são utilizadas?
Principalmente para a redução de complexidade de um algoritmo
Quais as partes obrigatórias de uma sub-rotina?
Nome, tipo de retorno e corpo da função
Qual a diferença entre função e procedimento?
Funções retornam valores, enquanto procedimentos não retornam nada
Cite algumas vantagens de sub-rotinas:
- Torna o algoritmo mais legível
- Podem ser testadas individualmente
- São independentes
- Podem ser reutilizadas
- Facilitam a manutenção do algoritmo
O que são vetores?
Uma lista de variáveis com mesmo tipo primitivo armazenada na memória de maneira sequencial
O que são registros?
Uma lista de variáveis que podem ter diferentes tipos primitivos, armazenada na memória de maneira sequencial
O que são ponteiros?
Variáveis que armazenam o endereço na memória de outras variáveis
Qual a principal justificativa para o uso de ponteiros?
Gerenciar o armazenamento de endereços na memória
Quais pontos a análise de algoritmos leva em consideração?
A exatidão do algoritmo, o tempo de execução e o espaço que ocupa em memória
O que é análise assintótica?
Uma análise que descreve a complexidade de um algoritmo quando a entrada de dados se torna muito grande.
O que é definição recursiva?
Quando um item é definido, e aparece como parte da própria definição.
Como também é chamada a definição recursiva?
Definição Indutiva
Quais as partes de uma definição recursiva?
1 - Uma base, que determina um caso simples de item definido
2 - Um passo recursivo, onde os outros casos do item vão ser definidos com base nos casos anteriores
Onde a definição recursiva pode ser utilizada?
1 - Sequência de objetos
2 - Funções
3 - Conjuntos
O que é uma sequência de objetos?
Uma lista de objetos enumerados.
O que ocorre com uma sequência de objetos quando é recursiva?
Explicita o primeiro valor e define os próximos valores com base no inicial
Qual a definição recursiva de uma função?
Um domínio de inteiros não negativos com dois passos.
O que é o problema de Fibonacci?
Uma sequência infinita de números naturais, aonde a partir do terceiro o valor é obtido pela soma dos dois números anteriores.
Qual a fórmula do algoritmo de Fibonacci?
F(n) = F(n-1) + F(n-2)
O que é um conjunto?
Um conjunto de valores finitos e desordenados.
Quais as 3 leis da recursividade?
1 - Deve ter um caso básico
2 - Deve mudar seu estado e se aproximar do caso básico
3 - Deve chamar a si mesmo
Quais os tipos de recursividade?
1 - Em cauda
2 - Indireta
3 - Aninhada
O que é a recursividade em cauda?
Quando a função chama ela mesmo no final da sua execução
O que é a recursividade indireta?
Quando uma função A chama a função B, e a função B chama a função A novamente.
O que é recursividade aninhada?
Quando uma função recursiva chama outra função recursiva dentro de si.
Qual a principal vantagem da recursividade?
Simplicidade, podendo resolver um problema com poucas linhas
Qual a principal desvantagem de recursividade?
A chamada em loop e o empilhamento de ações
O que é ordenação?
É o método de organizar um conjunto de objetos em ordem ascendente ou descendente
Qual o objetivo da ordenação?
Facilitar a recuperação dos itens de um conjunto
Com base em que a ordenação é feita? E quais as mais comuns?
É feita com base em uma chave de ordenação. E, as chaves de ordenação mais comuns são:
- Ordem numérica
- Ordem alfabetica (lexicográfica)
Quais os tipos de ordenação?
1 - Interna (IN-PLACE)
2 - Externa
Quando uma ordenação é interna?
O conjunto de dados é pequeno e cabe na memória principal. O processo de ordenar é realizado na memória principal.
Quando a ordenação é externa?
Quando o conjunto de dados não cabe todo na memória principal.
Podendo estar em um disco externo em formato de registro que serão acessados sequencialmente
Como funciona o bubble sort?
Comparando o elemento da vez ao próximo. Se não estiver na ordem correta, são trocados. Isso é repetido até que todas as trocam sejam feitas
Qual complexidade do algoritmo bubble sort?
O(n²)
Como funciona o insertion sort?
Verificando cada item por vez, e inserindo ele em seu devido lugar na lista.
Qual a complexidade do algoritmo insertion sort?
O(n²)
Como funciona o selection sort?
Selecionando o melhor elemento para ocupar uma posição no array a cada execução.
Qual a complexidade do selection sort?
O(n²)
Qual o tipo dos algortimos merge sort e quick sort?
Dividir para conquistar
Como funciona o merge sort?
Nele, o vetor é divido em vetores com a metade do tamanho original. Isso acontece até que o vetor tenha somente um item, e esteja ordenado e intercalado
Qual a complexidade do merge sort?
O(N log2 N)
Como funciona o quick sort?
Divide o vetor em duas partes, e faz isso até que o vetor tenha apenas um item, enquanto os outros ficam ordenados.
Qual a complexidade do quick sort?
No pior caso: O(n²),
No melhor caso: O(N log N)
De qual algoritmo o shell sort é derivado e como ele funciona?
É derivado do insertion sort e funciona com base na diminuição de incrementos
Qual a complexidade do shell sort?
O(n^1.25)
Pois quais elementos uma árvore binária T é composta?
Por um objeto N chamado de nó raiz, e por galhos Te e Td
