Vamos falar sobre algoritmos. Os novatos muitas vezes os percebem como algo difícil, complexo e incompreensível, e isso é parcialmente verdade, mas os algoritmos são a base. E quanto melhor você conhecer os fundamentos de sua especialidade, mais chances terá de se destacar nela.
Hoje vamos dar uma olhada em um belo problema de algoritmo. Não assustaremos as pessoas de trabalhar com algoritmos logo no início, então em nossa análise não haverá árvores de segmentos em expansão, nenhuma otimização variada do problema da mochila ou testes probabilísticos de simplicidade. Algos amigáveis ao usuário.
Aqui está o desafio: encontre a diferença máxima entre vizinhos.
Uma matriz de N inteiros é fornecida. Não é ordenado de forma alguma e os números podem ser repetidos. Digamos que o classificamos e calculamos a diferença entre cada par de elementos consecutivos. É necessário encontrar o máximo dessa diferença e fazê-lo da forma mais otimizada.
Complicado? Você pode tentar fazer isso antes de clicar em "Leia mais" e, em seguida, verificar a solução.
Então vamos. Diferença máxima entre vizinhos.
Considere um exemplo:
Deixe uma matriz de N = 11 elementos ser fornecida.
Primeiro, vamos resolver o problema de maneira ingênua, isso geralmente ajuda. Podemos fazer exatamente o que o problema exige de nós - classificar os números e encontrar a diferença entre os elementos adjacentes. A complexidade da solução irá variar dependendo da classificação que usamos.
Se usarmos qsort ou mergesort , a complexidade do tempo é... Se sabemos que os números são distribuídos de forma bastante densa no conjunto de inteiros, podemos usar a classificação por contagem. Então nós temos, onde U é a diferença entre o elemento máximo e mínimo. O caso é relativamente raro, mas vale lembrar dessa possibilidade.
Após a classificação, obtemos uma matriz:
Vamos escrever uma série de diferenças:
Concluímos que a diferença máxima é 6.
Agora vamos pensar, é possível resolver o problema mais rápido? Ao iterar sobre pares de elementos vizinhos, consideraremos muitos pares com uma pequena diferença. Esses pares podem nunca ser capazes de dar a maior diferença. Na verdade, na matriz classificada, temos um par de números adjacentes, seja a diferença entre o máximo e o mínimo ... Então, a maior diferença deve ter pelo menos... Esta estimativa é verdadeira pelo princípio de Dirichlet.
Se os pombos forem colocados em gaiolas e o número de pombos for maior do que o número de gaiolas, então pelo menos uma das gaiolas contém mais de um pombo.
9 células contêm 10 pombos, de acordo com o princípio de Dirichlet, pelo menos uma célula contém mais de um pombo ( Wikipedia )
Let, ... ,- i-ésimo elemento da matriz classificada. Então...
Se assumirmos que o máximo de todos os D [i] é menor, então todo o montante será estritamente menor que U, uma contradição.
Ótimo, temos um limite inferior para a diferença máxima! Agora vamos tentar localizar de alguma forma os elementos que estão muito próximos uns dos outros - dividimos o segmento do elemento mínimo para o máximo em meio-intervalos de comprimento... Cada elemento cairá exatamente em meio intervalo. Obteremos uma partição de todos os elementos em grupos não sobrepostos, também chamados de lotes.
É muito simples determinar em qual deles o elemento x caiu - você precisa calcular 1 + int ((x - a_min) / L) (nós numeramos de um), onde a_min é o elemento mínimo na matriz A, pode ser encontrado em uma passagem a matriz original. A única exceção será o elemento máximo - é melhor fazer os elementos com esse valor em um lote separado.
A figura mostra a distribuição do exemplo descrito acima. Para maior clareza, vamos fazer isso com nossas mãos:
A distribuição em lote é realizada em tempo linear e requer memória adicional. Observe que os itens de um lote não podem dar a diferença máxima entre dois itens. Selecionamos especialmente seu tamanho desta forma.
Onde pode haver dois elementos adjacentes? Claro, em lotes vizinhos não vazios! Por exemplo, na figura, os elementos do terceiro e do sexto lotes podem ir em uma linha em uma matriz classificada, desde que os lotes entre eles estejam vazios. É claro que apenas dois elementos serão adjacentes - o máximo do 3º lote e o mínimo do 6º. Da mesma forma, os candidatos a um par com a diferença máxima serão o elemento máximo do primeiro lote e o elemento mínimo do terceiro.
Vamos anotar todos os pares possíveis de elementos que podem dar a maior diferença. Vamos denotar como min (i) - o elemento mínimo no i-ésimo grupo, como max (i) - o elemento máximo.
máx (1) = -1 min (3) = 3
máx (3) = 4 min (6) = 10
máx (6) = 10 min (8) = 15
máx (8) = 15 min (10) = 20
máx (10) = 21 min (11) = 22
Identificamos pares que valem a pena considerar. Na prática, é necessário fazer uma passagem por todos os lotes, manter o último lote não vazio e o valor máximo do mesmo. Quando encontrarmos o próximo lote não vazio, encontraremos o mínimo nele e tentaremos atualizar a resposta.
Teremos o maior prazer - resolvemos o problema a tempo...
Na verdade, usamos uma ideia bastante conhecida e, de fato, demos os primeiros passos da classificação por bolso, no original é chamada de classificação por balde .
Os itens são organizados em cestas e, em seguida, os itens em cada cesta são classificados.
Na pior das hipóteses, funciona para, mas o tempo médio de execução com um número suficiente de lotes e uma distribuição uniforme de elementos é ...
“Mas espere, mas e o caso quando, por que você não pensou nisso? ”- o leitor atento perguntará. Este caso é degenerado, então não o consideramos, mas vamos fazer isso agora para completar.
Se a diferença entre o mínimo e o máximo for zero, a diferença máxima também será zero. Na verdade, isso é tudo.