Complexidade do algoritmo

Olá! A palestra de hoje será um pouco diferente das demais. Será diferente porque está apenas indiretamente relacionado ao Java. No entanto, este tópico é muito importante para todo programador. Falaremos sobre algoritmos . O que é um algoritmo? Em termos simples, esta é uma certa sequência de ações que devem ser executadas para alcançar o resultado desejado . Freqüentemente usamos algoritmos na vida cotidiana. Por exemplo, todas as manhãs você se depara com uma tarefa: vir para a escola ou para o trabalho e ao mesmo tempo ser:

• Vestido
• Limpar
• Bem alimentado

Qual algoritmo permitirá que você alcance esse resultado?

1. Acorde com um despertador.
2. Tome um banho, lave o rosto.
3. Prepare o café da manhã, faça café/chá.
4. Comer.
5. Se você não passou suas roupas desde a noite, passe-as.
6. Vestir-se.
7. Saia de casa.

Esta sequência de ações certamente permitirá que você obtenha o resultado desejado. Na programação, o objetivo do nosso trabalho é resolver problemas constantemente. Uma parte significativa dessas tarefas pode ser realizada utilizando algoritmos já conhecidos. Por exemplo, você se depara com uma tarefa: classificar uma lista de 100 nomes em um array . Esta tarefa é bastante simples, mas pode ser resolvida de diferentes maneiras. Aqui está uma solução: Algoritmo para classificar nomes em ordem alfabética:

1. Compre ou baixe na Internet o “Dicionário de Nomes Pessoais Russos”, edição de 1966.
2. Encontre todos os nomes da nossa lista neste dicionário.
3. Escreva em um pedaço de papel em qual página do dicionário o nome está.
4. Coloque os nomes em ordem usando as anotações em um pedaço de papel.

Essa sequência de ações nos permitirá resolver nosso problema? Sim, isso permitirá completamente. Esta solução será eficaz ? Dificilmente. Aqui chegamos a outra propriedade muito importante dos algoritmos – sua eficiência . O problema pode ser resolvido de diferentes maneiras. Mas tanto na programação quanto no dia a dia, escolhemos o método que será mais eficaz. Se a sua tarefa é fazer um sanduíche com manteiga, você pode, claro, começar semeando trigo e ordenhando uma vaca. Mas esta será uma solução ineficaz - levará muito tempo e custará muito dinheiro. Para resolver seu problema simples, você pode simplesmente comprar pão com manteiga. E o algoritmo com trigo e vaca, embora permita resolver o problema, é complexo demais para ser aplicado na prática. Para avaliar a complexidade dos algoritmos na programação, foi criada uma notação especial chamada Big-O ("big O") . Big-O permite estimar quanto o tempo de execução de um algoritmo depende dos dados passados ​​​​para ele . Vejamos o exemplo mais simples - transferência de dados. Imagine que você precisa transmitir algumas informações na forma de um arquivo a uma longa distância (por exemplo, 5.000 quilômetros). Qual algoritmo será o mais eficiente? Depende dos dados com os quais ele tem que trabalhar. Por exemplo, temos um arquivo de áudio de 10 megabytes. Neste caso, o algoritmo mais eficiente seria transferir o arquivo pela Internet. Isso levará apenas alguns minutos! Então, vamos expressar nosso algoritmo novamente: “Se você precisa transferir informações na forma de arquivos a uma distância de 5.000 quilômetros, você precisa usar a transmissão de dados pela Internet”. Ótimo. Agora vamos analisar isso. Isso resolve nosso problema? Em geral sim, resolve completamente. Mas o que você pode dizer sobre sua complexidade? Hmm, agora é aqui que as coisas ficam interessantes. O facto é que o nosso algoritmo depende muito dos dados recebidos, nomeadamente do tamanho dos ficheiros. Agora temos 10 megabytes e está tudo bem. E se precisarmos transferir 500 megabytes? 20 gigabytes? 500 terabytes? 30 petabytes? Nosso algoritmo irá parar de funcionar? Não, todas essas quantidades de dados ainda podem ser transferidas. Levará mais tempo para ser concluído? Sim vai! Agora conhecemos uma característica importante do nosso algoritmo: quanto maior o tamanho dos dados a serem transferidos, mais tempo o algoritmo levará para ser concluído . Mas gostaríamos de entender mais precisamente como é essa relação (entre o tamanho dos dados e o tempo que leva para transferi-los). No nosso caso, a complexidade do algoritmo será linear. “Linear” significa que à medida que o volume de dados aumenta, o tempo para sua transmissão aumentará aproximadamente proporcionalmente. Se houver 2 vezes mais dados, levará 2 vezes mais tempo para transferi-los. Se houver 10 vezes mais dados, o tempo de transferência aumentará 10 vezes. Usando a notação Big-O, a complexidade do nosso algoritmo é definida como O(N) . Esta notação é melhor lembrada para referência futura; ela é sempre usada para algoritmos com complexidade linear. Observação: não estamos falando aqui sobre várias coisas “variáveis”: velocidade da Internet, potência do nosso computador e assim por diante. Ao avaliar a complexidade de um algoritmo, isso simplesmente não faz sentido - de qualquer maneira, não temos controle sobre ele. Big-O avalia o próprio algoritmo, independente do “ambiente” em que ele terá que funcionar. Vamos continuar com nosso exemplo. Digamos que eventualmente o tamanho dos arquivos a serem transferidos seja de 800 terabytes. Se os transmitirmos pela Internet, o problema, claro, estará resolvido. Só há um problema: a transmissão através de um link moderno padrão (a 100 megabits por segundo) que a maioria de nós usa em casa levará aproximadamente 708 dias. Quase 2 anos! :O Então, nosso algoritmo claramente não é adequado aqui. Precisamos de alguma outra solução! De repente, a gigante de TI Amazon vem em nosso auxílio! Seu serviço Amazon Snowmobile permite carregar grandes quantidades de dados em unidades de armazenamento móveis e entregá-los no endereço desejado por caminhão! Portanto, temos um novo algoritmo! “Se você precisar transferir informações na forma de arquivos a uma distância de 5.000 quilômetros, e o processo demorar mais de 14 dias quando transferido pela Internet, será necessário usar o transporte por caminhão da Amazon.” O número de 14 dias foi escolhido aqui aleatoriamente: digamos que este é o período máximo que podemos pagar. Vamos analisar nosso algoritmo. E quanto à velocidade? Mesmo que o camião viaje a apenas 50 km/h, percorrerá 5.000 quilómetros em apenas 100 horas. São pouco mais de quatro dias! Isto é muito melhor do que a opção de transmissão pela Internet. E quanto à complexidade desse algoritmo? Também será linear, O(N)? Não, não vai. Afinal, o caminhão não se importa com o quanto você o carrega - ele ainda dirigirá aproximadamente na mesma velocidade e chegará na hora certa. Quer tenhamos 800 terabytes ou 10 vezes mais dados, o caminhão ainda chegará lá em 5 dias. Ou seja, o algoritmo de entrega de dados via caminhão tem complexidade constante . “Constante” significa que não depende dos dados passados ​​ao algoritmo. Coloque um pen drive de 1GB no caminhão e ele chegará em 5 dias. Coloque lá discos com 800 terabytes de dados e eles chegarão em 5 dias. Ao usar Big-O, a complexidade constante é denotada como O(1) . Desde que nos familiarizamos com O(N) eO(1) , vamos agora ver mais exemplos de “programadores” :) Digamos que você receba um array de 100 números e a tarefa seja imprimir cada um deles no console. Você escreve um loop regular forque executa esta tarefa

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Qual é a complexidade do algoritmo escrito? Linear, SOBRE. O número de ações que o programa deve executar depende exatamente de quantos números foram passados ​​para ele. Se houver 100 números no array, haverá 100 ações (saídas na tela), se houver 10.000 números no array, 10.000 ações precisarão ser executadas. Nosso algoritmo pode ser melhorado? Não. De qualquer forma, teremos que fazer N passagens pelo array e realizar N saídas para o console. Vejamos 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 LinkedListno qual inserimos vários números. Precisamos estimar a complexidade do algoritmo para inserir um único número em LinkedListnosso exemplo e como isso depende do número de elementos da lista. A resposta é O(1) - complexidade constante . Por que? Atenção: cada vez inserimos um número no início da lista. Além disso, como você lembra, ao inserir números em LinkedListelementos, eles não são deslocados para lugar nenhum - os links são redefinidos (se de repente você esqueceu como funciona o LinkedList, dê uma olhada em uma de nossas palestras antigas ). Se agora o primeiro número da nossa lista for o número х, e inserirmos o número y no início da lista, tudo o que é necessário é:

x.previous  = y;
y.previous = null;
y.next = x;

Para esta redefinição de referência, não nos importa quantos números existem agoraLinkedList - pelo menos um, pelo menos mil milhões. A complexidade do algoritmo será constante - O(1).

Complexidade logarítmica

Não entrar em pânico! :) Se a palavra “logarítmico” dá vontade de encerrar a palestra e não continuar lendo, espere alguns minutos. Não haverá dificuldades matemáticas aqui (existem muitas explicações desse tipo em outros lugares), e analisaremos todos os exemplos “nos dedos”. Imagine que sua tarefa é encontrar um número específico em uma matriz de 100 números. Mais precisamente, verifique se existe. Assim que o número necessário for encontrado, a busca deverá ser interrompida e a entrada “O número necessário foi encontrado!” deverá ser exibida no console. Seu índice no array = ....” Como você resolveria esse problema? Aqui a solução é óbvia: você precisa percorrer os elementos do array um por um, começando pelo primeiro (ou último) e verificar se o número atual coincide com o desejado. Conseqüentemente, o número de ações depende diretamente do número de elementos na matriz. Se tivermos 100 números, precisamos ir para o próximo elemento 100 vezes e verificar se o número corresponde 100 vezes. Se houver 1.000 números, haverá 1.000 etapas de verificação. Isso é obviamente uma complexidade linear, O(N) . Agora vamos acrescentar um esclarecimento ao nosso exemplo: o array no qual você precisa encontrar um número é classificado em ordem crescente . Isso muda alguma coisa em nossa tarefa? Ainda podemos procurar o número desejado por força bruta. Mas podemos usar o conhecido algoritmo de pesquisa binária . Na linha superior da imagem, vemos um array classificado. Nele precisamos encontrar o número 23. Em vez de iterar sobre os números, simplesmente dividimos o array em 2 partes e verificamos o número médio do array. Encontramos o número que está localizado na célula 4 e verificamos (segunda linha da imagem). Este número é 16 e estamos procurando 23. O número atual é menor. O que isto significa? Que todos os números anteriores (que estão localizados até o número 16) não precisam ser verificados : com certeza serão menores que o que procuramos, porque nosso array está ordenado! Vamos continuar a busca entre os 5 elementos restantes. Prestar atenção:Fizemos apenas uma verificação, mas já eliminamos metade das opções possíveis. Restam apenas 5 elementos. Repetiremos nosso passo - dividiremos novamente o array restante por 2 e novamente pegaremos o elemento do meio (linha 3 na figura). Este número é 56 e é maior do que o que procuramos. O que isto significa? Que descartamos mais 3 opções - o próprio número 56 e dois números depois dele (eles são definitivamente maiores que 23, porque o array está classificado). Restam apenas 2 números para verificar (a última linha da figura) - números com índices de array 5 e 6. Verificamos o primeiro deles e é isso que procurávamos - o número 23! Seu índice = 5! Vejamos os resultados do nosso algoritmo e então entenderemos sua complexidade. (A propósito, agora você entende porque é chamado de binário: sua essência é dividir constantemente os dados por 2). O resultado é impressionante! Se estivéssemos procurando o número desejado usando a pesquisa linear, precisaríamos de 10 verificações, mas com a pesquisa binária fizemos isso em 3! Na pior das hipóteses, haveria 4 deles, se na última etapa o número que precisávamos fosse o segundo, e não o primeiro. E quanto à sua complexidade? Este é um ponto muito interessante :) O algoritmo de busca binária depende muito menos do número de elementos no array do que o algoritmo de busca linear (ou seja, enumeração simples). Com 10 elementos na matriz, a pesquisa linear precisará de no máximo 10 verificações e a pesquisa binária precisará de no máximo 4 verificações. A diferença é de 2,5 vezes. Mas para uma matriz de 1.000 elementos, a pesquisa linear precisará de 1.000 verificações e a pesquisa binária precisará de apenas 10 ! A diferença já é de 100 vezes! Prestar atenção:o número de elementos na matriz aumentou 100 vezes (de 10 para 1.000), e o número de verificações necessárias para pesquisa binária aumentou apenas 2,5 vezes - de 4 para 10. Se chegarmos a 10.000 elementos , a diferença é ainda mais impressionante: 10.000 verificações de pesquisa linear e um total de 14 verificações de binário. E mais uma vez: o número de elementos aumentou 1.000 vezes (de 10 para 10.000), mas o número de verificações aumentou apenas 3,5 vezes (de 4 para 14). A complexidade do algoritmo de pesquisa binária é logarítmica ou, na notação Big-O, O(log n) . Por que isso é chamado assim? Um logaritmo é o inverso da exponenciação. O logaritmo binário é usado para calcular a potência de 2. Por exemplo, temos 10.000 elementos que precisamos percorrer usando uma pesquisa binária. Agora você tem uma imagem diante de seus olhos e sabe que isso requer no máximo 14 verificações. Mas e se não houver nenhuma imagem diante de seus olhos e você precisar contar o número exato de verificações necessárias? Basta responder a uma pergunta simples: a que potência deve ser elevado o número 2 para que o resultado obtido seja >= o número de elementos que estão sendo verificados? Para 10.000 será a 14ª potência. 2 elevado à 13ª potência é muito pequeno (8192) Mas 2 elevado à 14ª potência = 16384 , este número satisfaz nossa condição (é >= o número de elementos na matriz). Encontramos o logaritmo - 14. É de quantas verificações precisamos! :) Algoritmos e sua complexidade são um tópico vasto demais para ser incluído em uma palestra. Mas saber disso é muito importante: em muitas entrevistas você receberá problemas algorítmicos. Para teoria, posso recomendar vários livros. Um bom lugar para começar é “ Grocking Algorithms ”: embora os exemplos do livro sejam escritos em Python, a linguagem e os exemplos do livro são muito simples. A melhor opção para um iniciante, e também de pequeno volume. Leitura mais séria: livros de Robert Laforet e Robert Sedgwick . Ambos são escritos em Java, o que tornará o aprendizado um pouco mais fácil para você. Afinal, você está bastante familiarizado com esse idioma! :) Para alunos com boa formação matemática, a melhor opção seria o livro de Thomas Corman . Mas você não ficará satisfeito apenas com a teoria! “Saber”!= “ser capaz” Você pode praticar a resolução de problemas de algoritmo no HackerRank e Leetcode . Os problemas daí são frequentemente usados ​​​​mesmo durante entrevistas no Google e no Facebook, então você definitivamente não ficará entediado :) Para reforçar o material da palestra, aconselho você a assistir a um excelente vídeo sobre Big-O no YouTube. Nos vemos nas próximas palestras! :)