Complejidad temporal de pares en doble bucle de matriz

Question

Sé que lo siguiente es: 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;
       }
   }
}

Pero, ¿debería algo como count = count + 1; ¿ser tomado en cuenta?Para predecir o inventar una ecuación de tiempo compleja, o usar notación de suma,

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

Answer 1

Es una tarea bien conocida "Comprobación de duplicados" y puede encontrarla, por ejemplo, en Tim Roughgarden - Algoritmos iluminados_ Parte 1_ Conceptos básicos-(2017) 42 página.Permítanme decir que, como aquí, en el libro se toma el último índice "i" como $n=$"array.length()" no tiene sentido, porque entonces el índice "j" se queda sin bordes.Pero esto no afecta nuestro conteo.

Como siempre, lo principal es elegir la operación para contar; aquí es "contar = contar + 1".Obviamente el mejor de los casos, es decirmenor cantidad de operaciones, es $0$.Y en el peor de los casos, es decir.cantidad máxima de operaciones, es la suma (lo corrijo en consecuencia tomando el índice "i" hacia arriba $n-1$) traído por ti $T(n)=1+2+\cdots+(n-1)=\frac{n(n-1)}{2}$ (consideramos el caso $n\geqslant 2$).

Ahora porque $\frac{n(n-1)}{2} \leqslant \frac{n\cdot 2n}{2}=n^2$, es fácil concluir, que el peor de los casos $T(n) \en O(n^2)$.

Answer 2

La complejidad temporal de un algoritmo depende del modelo de cálculo.Los algoritmos generalmente se analizan en la máquina RAM, en la que las operaciones básicas en palabras de máquina (como asignación, aritmética y comparación) cuestan $O(1)$.Una palabra de máquina tiene longitud. $O(\logn)$, dónde $n$ es el tamaño de la entrada.

En su caso, el tamaño de la entrada es al menos $n$ (definido como la longitud de array), y entonces count cabe en una sola palabra de máquina.Cada una de las operaciones básicas del algoritmo cuesta $O(1)$, por lo que la complejidad del tiempo general es $ heta(n^2)$, ya que el algoritmo ejecuta tantas operaciones básicas.