Encontrando o Elemento Máximo

Autores:- Devanshu Dalal , Yash Gaherwar

Análise de Complexidade de Tempo: -

Quantos de vocês já pensaram o que é a complexidade do tempo. Muitos pensam que está relacionado com o tempo e seria denotado em milissegundos ou outra unidade de tempo, mas é esse o caso. Vejamos que a complexidade do tempo é o número de operações primitivas envolvidas para realizar ou executar um algoritmo.

Mas então surge a pergunta: por que não medimos isso em termos de tempo?

A resposta é porque temos vários tipos de processador, alguns são rápidos, enquanto outros são lentos. Portanto, não fará sentido dizer que meu algoritmo funciona em 2 ms em um processador OctaCore de 8 GB de RAM. Nossa complexidade de tempo deve sempre ser independente do processador ou de qualquer outro fator externo. Essa é a razão pela qual medimos a complexidade do tempo como o número de operações primitivas que precisamos realizar.

Vamos passar para o nosso problema principal.

Todos nós já vimos um problema para encontrar o elemento máximo em uma determinada matriz.

Todos podem estar dizendo agora que é um problema fácil.

Sim, um problema muito fácil, mas quantos de vocês pensaram no número médio de operações envolvidas para encontrar o elemento máximo?

Vamos ver com um exemplo

Suponha que n = 3

Portanto, toda permutação possível de array para elementos entre 1 a 3 é

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

Temos um total de 6 arrays possíveis.

Vamos ver o número de atualizações envolvidas na variável max nas seguintes permutações, inicialmente tomando 1 elemento como elemento max.

Para [1,2,3]

Tomamos o primeiro elemento 1 como elemento máximo inicialmente max=1, update=0

Então 2>1, max =2, atualização=1

Então 3>2, max=3, atualização=2

Total de 2 atualizações necessárias

Vamos verificar [1,3,2]

Tomamos o primeiro elemento 1 como elemento máximo inicialmente max=1, update=0

Então, 3>1, max=3, atualização=1

Então 2, max=3, atualização=1

Total de 1 atualização necessária

Da mesma forma, calculamos para outra permutação de matriz

Permutação total = 6

Atualizações totais = 5

Atualização média = 5/6 = 0,83

Atualização média em termos de n = 18/05 = 0,27

Da mesma forma, se calcularmos para outros valores de n

Podemos ver aqui que as atualizações médias em termos de n estão diminuindo à medida que os valores de n aumentam.

Mas calculá-lo dessa maneira pode ser um algoritmo muito demorado.

Então vamos tentar formular uma relação de recorrência para que possamos resolver esse algoritmo em uma complexidade de tempo melhor.

Como o valor de atualização em termos de n está diminuindo, podemos vê-lo como algum link com média harmônica.

Vamos ver,

A equação acima nos ajudaria a encontrar o não. de atualização média requerem em função de n.

Vamos encontrar a relação de recorrência para o mesmo

Assim, agora com a ajuda da relação de recorrência acima podemos encontrar a resposta em complexidade de tempo linear usando Programação Dinâmica.

Conclusão:-

Portanto, a partir da análise acima, descobrimos por que a Complexidade de tempo desempenha um papel importante para qualquer problema de estrutura de dados. Aqui fizemos a análise real de como o elemento máximo pode ser encontrado no array. E também fizemos a análise em diferentes permutações de matriz. Explicamos a Complexidade de tempo adequada na forma tabular para diferentes valores de n para que a análise adequada possa ser feita. Espero que isso seja útil para todos entenderem a Complexidade de maneira eficiente.