Please enable JavaScript.
Coggle requires JavaScript to display documents.
Complexidade dos algoritmos (Complexidade dos algoritmos (A ideia é medir…
Complexidade dos algoritmos
Complexidade dos algoritmos
Classifica problemas computacionais de acordo com a sua diiculdade inerente
Determina o custo (tempo, espaco...) p execucao de algoritmos
A ideia é medir o desempenho de um algoritmo. Como ? Investigando quantas vezes que operacoes sao executadas na execucao do algoritmo.
Notacao BIG-O: é uma representacao relativa da complexidade de um algoritmo. Representacao pq reduz a comparacao entre algoritmos a uma simples variavel por meio de observacoes e suposicoes.
No Big-O, O(n) significa que o numero de operacoes para ordenar um conjunto de n dados do algoritmo é diretamente proporcional a n. Entao se eu tenho 20 dados, preciso de 20 opercaoes. Se for O(n²), preciso de 400 operacoes para ordenar 20 dados.
Pior caso: Big-O
Medio caso: Big-Theta
Melhor caso: Big-Omega
Obs: Na notacao assintotica, é irrelaevante a base usada no logaritmo se ela for constante. Ex: tanto faz O(log 10n) ou O(log n)
Para comparar os algoritmos (quais que sao as funcoes maiores)
log(n)<long(n)^c<n<n log(n)<n²...<n!
Metodos de Ordenacao: Algoritmos que tem como objetivo principal posicionar os elementos de uma estrutura de dados em uma determinada ordem.
Métodos Estáveis:Bubble, Insertion e Merge
BubbleSort (Troca)
Em cada iteracao,compara-se o elemento com seu sucessor, trocando a posical se houver necessidade
se tiver n elementos, tem n-1 iteracoes e entao a lista fica em ordem crescente ou descrescente.
Se o elemento está na posicao i e tem que ir para posical j, percorre as posicoes entre i e j.
Pior caso: O(n²)
InsertionSort (Insercao)
Apresenta desemoenho melhor que Bubble em termos absolutos
Cada iteracao consiste em inserir o elemento da parte direita (pivô) na posicao adequada na parte esquerda, de modo que a esquerda continue ordenada.
Percorre os elementos deslocando os elementos estritamente maiores que o pivo uma posicao para direita.
Se a lista possui n elementos, após n-1 iteracoes chega ao ordenamento.
O pivo (aquele que ta sendo trocado) deve ser colocado imediatamente à esquerda do ultimo elemento movido.
Pior caso: O(n²)
Métodos Instáveis: Selection, Quick, Heap e Shell.
SelectionSort (Troca)
Consiste em selecionar o menor elemento de um vetor e trocá-lo pelo item que estiver na primeira posicao. Faz isso até o ultimo elemento do vetor
Desempenho costuma ser superior ao Bubble e inferior ao Insertion.
Cada iteracao consiste em pegar o menor elemento da parte direita(pivo) e trocá-lo com o primeiro elemento da parte esquerda.
Pior Caso: O(n²)
Resumo das complexidades: Bubbleshort: Melhor caso - O(n), Caso medio - O(n²), Pior caso - O(n²) ; InsrtionSort: O(n), O(n²), O(n²) ; SelectionSort: O(n²), O(n²), O(n²)
Pesquisa de Dados
Em geral, queremos que essa tarefa seja realizada sem ter que olhar toda a colecao de dados.
Maneiras de realizar pesquisa
Busca Binaria
Segue o paradigma de divisao-e-conquista: Parte do pressuposto de que o vetor esta em ordem crescente
Procedimento: Inspeciona-se a posicao central do vetor. Se o valor X estiver la, a busca para. Se nao, procura X recursivamente no intervalo do vetor entre a posicao inicial e a posicao central. Se nao der, faz recursivamente à direita de X.
Na verdade, vc quer procurar um valor e como ta em ordem crescente vai diminuindo os intervalor chegando sempre mais perto do valor. (Pela Mediana)
Complexidade O(log2n)
Busca sequencial: Inspenciono posicao por posicao (Em um vetor por exemplo) até encontrar um valor determinado.
Quanto maior o vetor e mais ao final o valor estiver mais demorado será.
Quando vetor é muito grande, esse método é inaceitavel.
Caso medio: Na metade do vetor
Pior caso: Ultima posicao do vetor
Melhor caso: primeira posicao a ser buscada