Tempo de complexidade de pares na matriz de double loop

Question

Eu sei, que é o seguinte: O(n^2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

Mas, se algo como count = count + 1; ser levado em conta?Para prever ou fazendo-se uma complexa equação de tempo, ou usando a notação de soma,

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

É conhecida a tarefa "Verificação de Duplicidades" e você pode encontrar, por exemplo, na Tim Roughgarden - Algoritmos Illuminated_ Parte 1_ O Básico-(2017) 42 página.Deixe-me dizer que, assim como aqui, então, no livro a tomar último índice "i" como $n=$"matriz.comprimento()" não tem nenhum sentido, porque então o índice "j" é executado fora de fronteiras.Mas isso não afeta a nossa contagem.

Como sempre o principal é escolher a operação de contagem - aqui a sua "count = count + 1".Obviamente, o melhor caso, por exemplo,menor quantidade de operações, é $0$.E o pior caso, isto é,montante máximo das operações, é a soma (I corrigi-lo em conformidade, tendo o índice "i" até $n-1$) trazida por você $T(n)=1+2+\cdots+(n-1)=\frac{n(n-1)}{2}$ (nós consideramos o caso $n\geqslant 2$).

Agora, porque $\frac{n(n-1)}{2} \leqslant \frac{n\cdot 2n}{2}=n^2$, é fácil concluir, que o pior caso $T(n) \em O(n^2)$.

Answer 2

O tempo de complexidade de um algoritmo depende do modelo de cálculo.Algoritmos são geralmente analisados na memória RAM da máquina, em que as operações básicas com máquina de palavras (como atribuição, aritméticos e de comparação) custo $S(1)$.Uma máquina palavra tem um comprimento $O( log n)$, onde $n$ é o tamanho da entrada.

No seu caso, o tamanho da entrada é de pelo menos $n$ (definido para ser o comprimento de array), e assim por count se encaixa em uma única máquina palavra.Cada uma das operações básicas no algoritmo de custo $S(1)$, e assim o tempo total de complexidade $ heta(n^2)$, uma vez que o algoritmo executa este número de operações básicas.