data structures and algorithms in swift

Estruturas de dados e algoritmos na escala

Estes são o resumo dos meus aprendizados de um curso de Udemy: "Estruturas de dados e Algo em Swift"

Complexidade do tempo:

1. Tempo constante
2. Tempo linear
3. Tempo quadrático
4. Tempo logarítmico - pesquisa binária
5. Tempo de Quasilinear

Nó:

• Raiz
• Criança -> Criança esquerda e criança direita
• Folha

Lista vinculada

• Os elementos estão conectados um ao outro por referência chamada nós

• 1º nó na lista vinculado é chamado de cabeça

• Último nó é chamado de nó de cauda

  Operações: - Push - Append - Insert - POP - RemoveLast - Remover

Stack (LIFO)

• Empurrar
• Pop

Fila (FIFO)

• Espiar
• Enquadre
• Dequeue

Recursão

• Caso base - que interrompe a recursão.
• Caso recursivo

Árvores:

• Profundidade Primeira travessia
• TRAVERSAL DE ORDEM DE NÍVEL
• Procurar
• Árvore binária (pode ter no máximo: 2 crianças apenas - esquerda e direita)
  • Em ordem Traversal -> Leftchild -> Node -> RightChild
  • Pós -ordem Traversal -> Leftchild -> RightChild -> Nó
  • PRAVERSAL pré -encomenda -> nó -> esquerda -> RETELCHILD
• Árvore de pesquisa binária

Pesquisa linear

• Sobre)

Pesquisa binária

• Matriz classificada
• Índice do meio - esquerda ou direita
• Melhor hora: o (1)
• Pior hora: o (log n)

Tipo de bolha

• Não classificado
• Melhor hora: O (n) (se já classificado)
• Pior hora: o (n^2)

Classificação de seleção

• Troque o elemento mínimo na matriz com o índice atual
• Mova para o próximo índice e repita a etapa 1
• Melhor hora: o (n^2)
• Pior hora: o (n^2)

Classificação de inserção

• Não classificado
• Melhor hora: O (n)
• Pior hora: o (n^2)

Gráfico:

Consiste em

• Vértices / vértice
• Bordas / Edge

Tipos de gráficos:

• Gráficos ponderados
• Gráficos direcionados
• Gráficos não direcionados (bidirecional)

Lista de adjacência

• Maneira mais comum/amplamente usada para criar e representar um gráfico