Oi! A lição de hoje será um pouco diferente das demais. Será diferente porque está apenas indiretamente relacionado ao Java. Dito isto, este tópico é muito importante para todo programador. Nós vamos falar sobre algoritmos . O que é um algoritmo? Em termos simples, é uma sequência de ações que devem ser concluídas para atingir um resultado desejado . Usamos algoritmos frequentemente na vida cotidiana. Por exemplo, todas as manhãs você tem uma tarefa específica: ir à escola ou ao trabalho e, ao mesmo tempo, ser:
- vestido
- Limpar
- federal
- Acorde usando um despertador.
- Tome um banho e lave-se.
- Faça o café da manhã e um pouco de café ou chá.
- Comer.
- Se você não passou suas roupas na noite anterior, passe-as.
- Vestir-se.
- Saia de casa.
- Compre ou baixe a edição de 1961 do Webster's Third New International Dictionary.
- Encontre todos os nomes da nossa lista neste dicionário.
- Em um pedaço de papel, escreva a página do dicionário em que o nome está localizado.
- Use os pedaços de papel para classificar os nomes.
for
loop comum que executa esta tarefa
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Qual é a complexidade desse algoritmo? Linear, ou seja, O(n). O número de ações que o programa deve executar depende de quantos números são passados para ele. Se houver 100 números na matriz, haverá 100 ações (declarações para exibir strings na tela). Se houver 10.000 números na matriz, 10.000 ações deverão ser executadas. Nosso algoritmo pode ser melhorado de alguma forma? Não. Não importa o que aconteça, teremos que fazer N passagens pelo array e executar N instruções para exibir strings no console. Considere outro exemplo.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Temos um vazio LinkedList
no qual inserimos vários números. Precisamos avaliar a complexidade algorítmica de inserir um único número em LinkedList
nosso exemplo e como isso depende do número de elementos na lista. A resposta é O(1), ou seja, complexidade constante . Por que? Observe que inserimos cada número no início da lista. Além disso, você deve se lembrar que quando você insere um número em um LinkedList
, os elementos não se movem para lugar algum. Os links (ou referências) estão atualizados (se você esqueceu como funciona o LinkedList, veja uma de nossas aulas antigas ). Se o primeiro número da nossa lista for x
, e inserirmos o número y no início da lista, tudo o que precisamos fazer é o seguinte:
x.previous = y;
y.previous = null;
y.next = x;
Quando atualizamos os links, não nos importamos quantos números já estão noLinkedList
, se um ou um bilhão. A complexidade do algoritmo é constante, ou seja, O(1).
GO TO FULL VERSION