Please enable JavaScript.
Coggle requires JavaScript to display documents.
data structures and algorithms - Coggle Diagram
data structures and algorithms
definições: data structures são diferentes jeitos de guardar informações no computador
exemplos
lugares e caminhos
guradar todas as os pares de ligações de cada "rua" (ARRAY OR LIST STRUCTURE)
no exemplo o computador teria que varrer toda a lista para saber executar o desejado.
Guardar a partir de um ponto, todo lugar que se pode ir a partir dele (HASHTABLE OR HASHMAP DATASTRUCTURE)
no exemplo, apo´s identificada o ponto de partida, não precisariamos andar a lista toda.
festa, cada um na festa tras uma bola com seu nome. e quero guardar qume veio e em que ordem.
caixa com 100 partições em linha. quando cada m chegar colocará sua bola em ordem. (ARRAY)
Vantagens: Localizar uma caizxa individual é mais fácil e rápido, sabemos onde cada info está pois temos a distância exata.
Desvantagens: para criar novos espaços "caixas" para mais informaçãoe é mais dificil poderia apagar a caixa existente e colocar tudo em uma ciaxa maior, pegar outras caixa do mesmo tamanho e trabalhar com as duas ao mesmo tempo.
Caixas individuais que estão conectadas por uma corda. (LINKED LIST STRUCTURE)
desvantagens: Localizar uma caixa pode ser mais difícil pois cada caixa pode estar em um lugar pois a "corda" junta as caixas. e para chegar em uma específica vc tem que contar uma por uma.
Vantagens: caso apareca mais gente na festa = muito fácil criar novas "caixas" para informação extra.
Algoritimos
set of intructions to accomplish some task
different data structures need different algorithms.
RECURSION
FUNÇÃO QUE CHAMA A SI MESMA, E VAI DEIXANDO VARIAVEIS "ABERTAS" ATÉ ESBARRAR EM SOLUÇÃO TRIVIAL E VOLTAR PREENCHENDO TODOS OS RESULTADOS ABERTOS.
tipos de dados e memória
ARRAYS
COMUM: Cada lista ter apenas um tipo de informação, ex: lista só de strings
CAIXAS SEQUENCIAIS E ORGANIZADAS GEOMETRICAMENTE, SEI ONDE ENCONTRAR CADA CAIXA.
MEMÓRIA
RAM (INFORMAÇÃO TEMPORÁRIA)
STORAGE (FLASH DRIVE, HARD DISK, SOLID STATE DRIVE) INFORMAÇÃO PERMANENTE
MECANISMOS
OS DOCUMENTOS PERMANENTES NA STORAGE SÃO CARREGADOS PARA A MEMÓRIA RAM POIS É MAIS RÁPIDO DE TER ACESSO AOS DOCUMENTOS ENQUANTO O COMPUTADOR ESTA LIGADO.(MELHOR DO QUE ACESSAR A STORAGE TODA HORA (LENTO), NA HORA DE SALVAR ATUALIZA AS MUDANÇAS NA STORAGE.
PARA APLICAÇÕES: elas ficam guardadas no storage mas são carregadas na RAM . por isso se abrir muito apps pode ficar sem memoria RAM.
COMO SÃO GUARDADAS AS INFORMAÇÕES: CADA INTEIRA USA 32 BITS OU 64BITS. A MEMÓRIA FUNCIONA EM PACOTES DE BYTES, CADA BYTES = 8 BITS. CADA BYTE TEM SEU ENDEREÇO.EX: SE USARMOS 32BIT, PRECISAMOS DE 4 BYTES PARA GUARDAR UM NÚMERO INTEIRO.
PARA GUARDAR ARRAYS: COMO A MEMÓRIA É SEQUENCIAL QUANDO VOCÊ GUARDA UMA LISTA EX: {1,2,3} A MEMÓRIA IRÁ PRECISAR DE 4X4 = 12 BYTES PARA GUARDAR OS NÚMEROS, E QUANDO PULAR PARA PROXIMA LINHA DO CÓDIGO CONTINUARA A PREENCHER OS BYTES SEGUINTES (SEQUENCIAIS COMO UMA FILA ÚNICA) COM OUTRAS INFOS, ENTÃO SE VOCÊ QUISER ADICIONAR MAIS NUMEROS AO ARRAY OS PRÓXIMOS BYTES AO LADO DOS BYTES DA LISTA JÁ ESTARÃO UTILIZADOS E VOCÊ TERÁ QUE CRIAR OUTRO ARRAY COM MAIS ESPAÇO, COPIAR OS DADOS ANTIGOS E JUNTAR AOS NOVOS.
OBJECTS
COLEÇÃO DE PROPRIEDADES QUEM PODEM SER EXPRESSAS COMO VARIÁVEIS E FUNÇÕES.
VARIÁVEIS DENTRO DOS OBJETOS = INSTANCE VARIABLE ATTRIBUTES
FUNÇÕES DENTRO DO OBJETO: METHODS
CLASS.
É UM TEMPLATE DE OBJECTS COM AS FUNÇÕES E VARIÁVEIS VAZIAS
PRECISA TER UM NOME QUE A DEFINA
CONSTRUCTOR
FUNÇÃO (DENTRO DA CLASSE) QUE TE PERMITE CRIAR UM OBJETO A PARTIR DA CLASSE, E CONFIGURA OS ATRIBUTOS PARA VOCÊ.
AS LINGUAGENS JA VEM COM CUSTROCTORS DEFAULT, SE VOCÊ DEFINE UM NOVO VOCÊ INUTILIZA OS DEFAULT.
DEIXA A ESCRITA DO CÓDIGO MAIS SIMPLES POIS JÁ FAZ ATIBUIÇÕES PARA VOCÊ E VOCÊ SÓ PASSA OS ARGUMENTOS.
LINKED-LIST
"CAIXAS CONECTADAS" EU SEMPRE SEI QUEM É A PROXIMA, MAS NUNCA CONSIGO VOLTAR PARA ANTERIOR.
Class box (para linked-list), te´ra os atributos data(informação que a caixa guarda) and next(quem é a proxima caixa)
A CLASS BOX( PARA UM ESPAÇO DE INFORMAÇÃO NA LINKED LIST É CHAMADA DENTRO DO CÓDIGO COMO "NODE" PORTANTO BOX = NODE.
DOUBLY-LINKED LIST, TEM O PARAMETRO PARA VOLTAR A CAIXA ANTERIOR.
BIG O NOTATIONS AND TIME COMPLEXITY
RELAÇÃO DO TAMANHO DE INPUT NA SUA FUNÇÃO COM O TEMPO PARA RODAR SUA FUNÇÃO.
PERGUNTA 1: QUANTO TEMPO VAI DEMORAR PARA MEU COMPUTAOR RODAR A FUNÇÃ? é uma pergunta genérica pois dependede muito outros fatores como que computador você tem, que linguagem está usando, quantos outros programas estão rodando ao mesmo tempo.
PERGUNTA 2: COMO O TEMPO PARA RODAR CRESCE DE ACORDO COM P CRESCIMENTO DO INPUT (EX: UMA LISTA). PARA RESPONDER ESSA PODEMOS USAR BIG O NOTATION E TIME COMPLEXITY
TIME COMPLEXITY
UMA MANEIRA DE MOSTRAR COMO O TEN=MPO PARA RODAR A FUNÇÃO AUMENTA. EX: LINEAR TIME -> O TEMPO AUMENTA LINEAR MENTE COM O TAMANHO DO INPUT.
LINEAR TIME
CONSTANT TIME
QUADRATIC TIME
BIG O NOTATION
FORMA MATEMÁTICA DE REPRESENTAR OS TIPOS DE TIME COMPLEXITY
LINEAR = O(n)
CONSTANT = O(1)
QUADRATIC = O(n²)
regras para achar a big o notation: 1 - ache na equações o termo que crece mais rápido. 2-- tire o coefiecente, o que sobra "x" a notação fica O(x)
ACHAR O BIG O DE UMA FUNÇÃO, BASTA ACHAR O BIG O DE CADA LINHA E SOMAR TODOS OS BIG O´S. Considera n = numero de elementos em cada array, se o input for uma "matriz quadrada" , o número todas de vezes que uma linha soma total =+ 1 de while vai rodar é n².