¿Cómo encuentro la complejidad temporal T (n) y demuestro que está estrechamente limitada (Big Theta)?

Question

Estoy tratando de descubrir cómo dar una complejidad de tiempo en el peor de los casos. No estoy seguro de mi análisis. He leído anidado para bucles grandes O es n ^ 2 ; ¿Es esto correcto para un bucle for con un bucle while dentro?

// A is an array of real numbers.
// The size of A is n. i,j are of type int, key is
// of type real. 
Procedure IS(A)    
for j = 2 to length[A]     
{                
   key = A[ j ]               
   i = j-1   
   while i>0 and A[i]>key    
   {       
      A[i+1] = A[i]                         
      i=i-1                    
   }                
   A[i+1] = key      
}

hasta ahora tengo:

j=2 (+1 op)  

i>0 (+n ops)   
A[i] > key (+n ops)

so T(n) = 2n+1?  

Pero no estoy seguro de si tengo que entrar en los bucles while y for para analizar una complejidad de tiempo de caso peor ...

Ahora tengo que demostrar que está bien unido, eso es Big theta.

He leído que los bucles anidados para tienen Big O de n ^ 2 . ¿Es esto también cierto para Big Theta? Si no, ¿cómo haría para encontrar Big Theta?

** C1 = C sub 1, C2 = C sub 2, y no = n nada son elementos de números reales positivos

Para encontrar el T (n) miré los valores de j y miré cuántas veces se ejecutó el ciclo while:

values of J:   2, 3, 4, ... n  
Loop executes: 1, 2, 3, ... n

Análisis:
Tome la suma de las ejecuciones del bucle while y reconozca que es (n (n + 1)) / 2 Asignaré esto como mi T (n) y probaré que está estrechamente limitado por n ^ 2 . Es decir n (n + 1) / 2 = & # 952; (n ^ 2)

Trabajo Scratch:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no

To make 0 ≤ C1(n) true, C1, no, can be any positive reals   
To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1  
To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1  

PF:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Let C1= 1/2, C2= 1 and no = 1.  

1. muestra que 0 & # 8804; C1 (n ^ 2) es cierto C1 (n ^ 2) = n ^ 2/2
        n ^ 2/2 & # 8805; no ^ 2/2
        & # 8658; no ^ 2/2 & # 8805; 0
        1/2 > 0
   Por lo tanto, C1 (n ^ 2) & # 8805; ¡0 es cierto!

2. muestra que C1 (n ^ 2) & # 8804; (n (n + 1)) / 2 es verdadero C1 (n ^ 2) & # 8804; (n (n + 1)) / 2
   n ^ 2/2 & # 8804; (n (n + 1)) / 2 n ^ 2 & # 8804; n (n + 1)
   n ^ 2 & # 8804; n ^ 2 + n
   0 & # 8804; n

   Esto sabemos que es verdad desde n & # 8805; no = 1
   Por lo tanto, C1 (n ^ 2) & # 8804; (n (n + 1)) / 2 se demuestra cierto!

3. Mostrar que (n (n + 1)) / 2 & # 8804; C2 (n ^ 2) es verdadero (n (n + 1)) / 2 & # 8804; C2 (n ^ 2)
   (n + 1) / 2 & # 8804; C2 (n)
   n + 1 & # 8804; 2 C2 (n)
   n + 1 & # 8804; 2 (n)
   1 & # 8804; 2n-n
   1 & # 8804; n (2-1) = n
   1 & # 8804; n
   Además, sabemos que esto es cierto desde n & # 8805; no = 1

   Por lo tanto, por 1, 2 y 3, & # 952; (n ^ 2) = (n (n + 1)) / 2 es verdadero ya que
   0 & # 8804; C1 (n ^ 2) & # 8804; (n (n + 1)) / 2 & # 8804; C2 (n ^ 2) para todos n & # 8805; no

Dime qué piensan ustedes ... ¡Estoy tratando de entender este material y me gustaría que me dieran su opinión!

Answer 1

Parece que está implementando el algoritmo de inserción , que según Wikipedia es O (N ² ).

Generalmente, desglosas componentes basados ??en tu variable N en lugar de tu constante C cuando trabajas con Big-O. En su caso, todo lo que necesita hacer es mirar los bucles.

Tus dos bucles son (en el peor de los casos):

for j=2 to length[A]
    i=j-1
    while i > 0
        /*action*/
        i=i-1

El bucle externo es O (N), porque se relaciona directamente con el número de elementos.

Observe cómo su ciclo interno depende del progreso del ciclo externo. Eso significa que (ignorando los problemas off-by-one) los bucles interno y externo están relacionados de la siguiente manera:

 j's     inner
value    loops
-----    -----
  2        1
  3        2
  4        3
  N       N-1
-----    -----
total    (N-1)*N/2

Entonces, el número total de veces que se encuentra / * action * / es (N ² - N) / 2, que es O (N ² ).

Answer 2

Mirar el número de bucles anidados no es la mejor manera de obtener una solución. Es mejor mirar el " trabajo " eso se hace en el código, bajo una gran carga N. Por ejemplo,

for(int i = 0; i < a.size(); i++)
{
  for(int j = 0; j < a.size(); j++)
  {
    // Do stuff
    i++;
  }
}

es O (N).

Una función f está en Big-Theta de g si está en Big-Oh de gy Big-Omega de g. El peor de los casos ocurre cuando los datos A están disminuyendo monotónicamente la función. Luego, para cada iteración del bucle externo, se ejecuta el bucle while. Si cada declaración aportó un valor de tiempo de 1, entonces el tiempo total sería 5 * (1 + 2 + ... + n - 2) = 5 * (n - 2) * (n - 1) / 2. Esto da Una dependencia cuadrática de los datos. Sin embargo, si los datos A son una secuencia monotónicamente creciente, la condición A [i] > La clave siempre fallará. Así, el bucle externo se ejecuta en tiempo constante, N - 3 veces. El mejor caso de f tiene una dependencia lineal de los datos. Para el caso promedio, tomamos el siguiente número en A y encontramos su lugar en la clasificación que ocurrió anteriormente. En promedio, este número estará en el medio de este rango, lo que implica que el ciclo while interno se ejecutará la mitad de las veces que en el peor de los casos, dando una dependencia cuadrática de los datos.

Answer 3

Big O (básicamente) acerca de cuántas veces se mirarán los elementos en su ciclo para completar una tarea.

Por ejemplo, un algoritmo O (n) iterará a través de cada elemento solo una vez. Un algoritmo O (1) no tendrá que recorrer en iteración todos los elementos, sabrá exactamente dónde buscar en la matriz porque tiene un índice. Un ejemplo de esto es una matriz o tabla hash.

La razón por la que un bucle dentro de un bucle es O (n ^ 2) es porque cada elemento del bucle tiene que iterarse sobre sí mismo ^ 2 veces. Cambiar el tipo de bucle no tiene nada que ver, ya que se trata esencialmente de # de iteraciones.

Existen enfoques para algoritmos que le permitirán reducir la cantidad de iteraciones que necesita. Un ejemplo de estos son " divide & amp; conquistar " algoritmos como Quicksort , que si recuerdo correctamente es O (nlog (n)).

Es difícil encontrar una mejor alternativa a su ejemplo sin saber más específicamente lo que está tratando de lograr.