Please enable JavaScript.

Coggle requires JavaScript to display documents.

Fundamentos da Estrutura da Informação, Algoritmos, Não ordenado,…

- - - - passos(não tempo)
      - varia pra cada Hardware
      - Complexidade temporal
    - - espaços de memória
      - Espaço adicional
      - eficiência
  - - - Um passo
      - Tamanho n importa
      - Eficiente em espaço
    - - Até (N) passos
      - Linear/Simples
      - eficiente no espaço
      - algoritimos
        
        Busca Linear
        
        O que ocorre com a busca por um elemento que não existe?
        
        Array ordenado
        
        Na maioria das vezes requer menos passos que o array regular
        
        Continua sendo N passos no pior caso, mas é melhor em geral
        
        O espaço utilizado é o mesmo da busca e da inserção no array
        regular
        
        Podemos parar assim que um valor maior for encontrado
        
        array comun(não ordenado
        
        percorre todo array
        
        Busca binaria
        
        epenas em array ordenado
        
        busca o iten dividindo o array
        
        O(log N)
    - - N + 1 passos
      - precisa de um espaço adicional para o novo valor
      - Eficiente no espaço
        
        espaço adicional não muda independente das
        entradas
        
        espaço adicional não muda independente da
        posição da inserção
    - - pior caso: N passos
      - eficiente no espaço
        
        O espaço adicional não muda independente das
        entradas
        
        espaço adicional não muda independente da
        posição da remoção
        
        espaço do array que fica livre por conta na remoção não,resulta em um saldo de espaço, pois esse espaço estava sendo usado durante a operação
- - - - tempo constante
    - - tempo crescente
    - - tempo crescente reduzido
    - - tempo linear
- - - - Função de Hash
        
        Mapeia chave para índice
        
        Uniformidade na distribuição
      - Tabela de Slots (Array)
        
        Slots/buckets para armazenar dados
      - Operações
        
        Inserção
        
        Aplicar função de hash à chave
        
        Armazenar valor no índice correspondente
        
        Tratar colisões
        
        Busca
        
        Aplicar função de hash à chave
        
        Encontrar valor no índice correspondente
        
        Tratar colisões
        
        Remoção
        
        Aplicar função de hash à chave
        
        Remover par chave-valo
        
        Tratar colisões
        
        Tratamento de Colisões
        
        Encadeamento (Chaining)
        
        Lista ligada em cada slot
        
        Endereçamento Aberto (Open Addressing)
        
        Sondagem linear
        
        Sondagem quadrática
        
        Duplo hashing
        
        Vantagens
        
        Eficiência: Operações O(1) no melhor caso
        
        Flexibilidade: Armazena pares chave-valor de qualquer tipo
        
        Desvantagens
        
        Colisões: Necessidade de tratamento eficiente
        
        Espaço: Possível desperdício de memória
        
        Função de Hash: Dependência da qualidade da função
- - - - Push (inserir)
      - Pop (remover)
      - Peek (consultar o topo)
      - isEmpty (verificar se está vazia)
      - Aplicações
        
        Algoritmos de backtracking
        
        Pilha de execução em linguagens de programação
        
        Algoritmos de reversão
        
        Vantagens
        
        Simplicidade de operações
        
        Desvantagens
        
        Limitação de acesso aos elementos (somente pelo topo)
- - - - Enqueue (inserir)
      - Dequeue (remover)
      - Front (consultar o início)
      - isEmpty (verificar se está vazia)
      - Aplicações
        
        Gerenciamento de tarefas em sistemas operacionais
        
        Algoritmos de busca em largura (BFS)
        
        Sistemas de atendimento
        
        Implementação (Exemplo em Python)
        
        Usando lista (list)
        
        Usando módulo collections.deque
        
        Vantagens
        
        Simplicidade de operações
        
        Desvantagens
        
        Acesso sequencial (primeiro ao último
- - - - Listas (list)
      - Tuplas (tuple)
      - Conjuntos (set)
      - Dicionários (dict)
- - - - Possuem o método especial iter().
      - Exemplos
        
        Listas
        
        Tuplas
        
        Conjuntos
        
        Dicionários
        
        Strings (str)
- - - - Possuem os métodos especiais iter() e next().
      - Utilizam StopIteration para sinalizar o fim da iteração.
      - Criação
        
        Obtido chamando iter() em um iterável
- - - - Utilizam a palavra-chave yield para produzir uma série de valores.
      - Retornam um gerador-iterador que pode ser usado em um loop for ou com next().
- - - - Atributo
        
        Metodos
        
        Encapsulamento
        
        Herança
        
        Polimorfismo
        
        Abstração
        
        1 more item...
        
        Capacidade de um objeto assumir várias formas, incluindo polimorfismo de subtipo e de sobrecarga.
        
        Mecanismo de reutilização de código, permitindo que uma subclasse herde de uma superclasse, suportando o polimorfismo e a sobrescrita de métodos.
        
        Princípio de ocultação de dados, utilizando interfaces públicas e implementações privadas, com getters e setters.
        
        Funções ou procedimentos associados a um objeto, incluindo métodos de instância e de classe, e a possibilidade de sobrecarga.
        
        Propriedades ou dados de um objeto, geralmente representados como variáveis de instância, com modificadores de acesso para controlar a visibilidade.
      - Um modelo ou template para objetos, definindo seus atributos e métodos, e podendo ser usada para herança.
- - - - Etapa 2
        
        Etapa 3
        
        Etapa 4
        
        Repetir as etapas 1 a 3 até ter uma passagem em que trocas não
        foram necessárias
        
        O array está ordenado
        
        Mover os ponteiros uma célula para a direita
        
        Repetir as etapas 1 e 2 até o final do array, ou até um elemento
        que já tenha sido ordenado
        
        Se estiverem fora de ordem, trocá-los de posição
        
        Caso contrário, não fazer nada
      - Apontar para dois itens consecutivos no array
        
        Comparar o primeiro com o segundo
    - - O(1)
    - - O(N^2)
  - - - Etapa 2
        
        Etapa 3
        
        Repetir as etapas 1 e 2 até que o array esteja ordenado
        
        – Cada repetição das etapas 1 e 2 é uma passagem
        
        Uma vez definido o índice de menor valor, sua posição é trocada
        com o valor no índice de início da passagem
        
        Índice zero para a primeira passagem, índice 1 para a segunda, ...
      - Verificar cada célula do array da esquerda para a direita
        
        Determinar o índice da célula com o menor valor
        
        A verificação começa à direita da última célula já ordenada
    - - O(N)
    - - O(N^2)
  - - - Etapa 2
        
        Etapa 3
        
        Etapa 4
        
        – Repetimos as etapas 1 a 3 até que array esteja ordenado
        
        Inserimos no espaço em branco o valor retirado
        temporariamente
        
        Inicia-se a fase de deslocamento
        
        Cada valor à esquerda do espaço vazio é comparado com a
        variável temporária
        
        Se o valor à esquerda for maior do que a variável temporária, ele
        é deslocado para a direita
        
        Os deslocamentos param ao se encontrar um valor menor que a variável temporária, ou o espaço livre ficar na célula mais à esquerda
      - Na primeira passagem, o valor no índice 1 é retirado e
        armazenado em uma variável temporária
    - - Pior caso: O(N^2)
        
        Caso médio: N^2/2