Estrutura de dados e ordenação Flashcards
Bubble Sort
Bubble sort é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
Para listas já ordenadas em ordem crescente é o único algoritmo que não realiza movimentações, mas em compensação é o que tem o maior tempo e o maior número de comparações. Não só em listas já ordenadas, mas em todos os casos o bubble sort se mostrou um algoritmo ineficiente.
Selection Sort
Este algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos.
Neste algoritmo de ordenação é escolhido um número a partir do primeiro, este número escolhido é comparado com os números a partir da sua direita, quando encontrado um número menor, o número escolhido ocupa a posição do menor número encontrado. Este número encontrado será o próximo número escolhido, caso não for encontrado nenhum número menor que este escolhido, ele é colocado na posição do primeiro número escolhido, e o próximo número à sua direita vai ser o escolhido para fazer as comparações. É repetido esse processo até que a lista esteja ordenada.
Nas listas de ordem 1 e ordem 3, o selection sort foi o segundo pior algoritmo, mas se mostrou mais eficiente do que o Insertion sort em relação ao tempo e a quantidade de movimentações na lista de ordem 2.
Insertion sort
O Insertion sort é um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados.
O algoritmo funciona da mesma forma que as pessoas usam para ordenar cartas em um jogo de baralho como o pôquer.
Na lista de ordem 1, o Insertion sort se mostrou mais eficiente que todos os outros algoritmos em relação ao tempo e comparações. Na lista de ordem 2 foi menos eficiente do que o selection sort e na lista de ordem 3 a diferença de tempo entre o insertion e o selection foi pequena.
Quick sort
O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.
O quick sort certamente é o algoritmo mais eficiente em listas totalmente desordenadas, ele se torna muito eficiente em relação aos outros no quesito de tempo. Na lista de ordem 3 e na de ordem 2 a diferença de tempo do quick sort em comparação aos outros foi absurdamente grande.
algoritmos de ordenação com complexidade O(n²)
Nesse grupo estão os algoritmos selection sort, bubble sort e insertion sort. Esses algoritmos são lentos para ordenação de grandes listas, porém são mais intuitivos de entender e possuem codificação mais simples.
arvore de decisão não pode ser usada para classificação e regressão
falso
quais são as 3 características que medem a eficiencia de uma arvore de decisão?
precisão, impureza de gini e entropia
o indice de impureza de gini mede a impureza de um conjunto?
verdadeiro
um conjunto em que cada elemento tem o mesmo rótulo tem um índice de impuerza de gini de 1
falso. tem o indice de impureza igual a 0
ao construir uma árvore de decisão, a diferença na entropia antes e depois de uma divisão é chamada de ganho de informação
verdadeiro
qual a estrutura de um aprendizado de máquina?
rebember
formulate
predict (prever)
palavras chave de aprendizado por reforço
politica
feedback
agente
ambiente
o método de regressão linear para predição consiste em atribuir um peso a cada uma das características e adicionar os pesos correspondentes multiplicados pelas características, além de um viés
verdadeiro
uma maneira eficas de diferenciar o sobreajuste e o subajuste é usando um conjunto de dados de treinamento
falso
é usando um conjunto de dados de teste
quais são os 3 passos do conjunto de dados de regularização (overfitin e under fiting)?
treino — validação —- teste
validação —–hiperparametro
parametro é ajustado pelo próprio modelo ao longo do aprendizado. por isso ele não é a mesma coisa que hiper parametro
a regularização l2 é recomendada quando nosso conunto dedados possui inúmeros recursos e queremos transformar muios deles em zero
falso,. isso é a regularização L1
a regularização l1 é recomendada quando noso conjutno dedados tem poucos recursos, e queremos torná-los pequenos, mas não zero
falso, isso é a regularização l2
rede neural pode ser usado para classificação e regressão?
verdadeiro
uma rede neural consiste em um conjutno de perceptrons organizados em camadas, onde a saída de uma camada serve como entrada para próxima camada
verdadeiro
as funções de ativdação de redes neuraos mais populares incluem sigmoide, tangente, hiperbólica, softmax e a unidade retificada (ReLU). Eles são usados entre camadas em uma rede neural para quebrar a linearidade e nos ajudar a construir limites mais complexos
verdadeiro
um dos processo que usamos para treinar a derivada da função de perda e encontrar todas as derivadas para atualizar os pesos do modelo iterativamente para melhorar seu desempenho
verdadeiro
comandos para usar na pilha
push – colocar dados
pop – retirar um elemento da pilha
peek – verifica o elemento que está na cabeça da pilha
o polimorismo de sobrecarga ocorre quanod há vários métodos com o mesmo nome em uma classe, mas com diferentes parâmetros.
verdadeiro
é possível fazer uma busca binária em uma lista?
não. somente me arrays
complexidade da busca binária
melhor caso: O(1)
médio / pior caso O(log2n)
