Complejidad del algoritmo

Cuál es la complejidad dada para el siguiente problema es O (n). ¿No debería ser O (n^2)? Esto se debe a que el ciclo externo es O (n) e interno también es O (n), por lo tanto n * n = O (n^2)?Complejidad del algoritmo

La hoja de respuestas de esta pregunta indica que la respuesta es O (n). ¿Cómo es eso posible?

public static void q1d(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n; j++) { 
      count++; 
     } 
    } 
}

La complejidad del siguiente problema es O (n^2), ¿cómo se puede obtener? ¿Puede alguien por favor elaborar?

public static void q1E(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n/2; j++) { 
      count++; 
     } 
    } 
}

Gracias

Fuente

2012-01-17 Harminder

Creo que el superior es O (n^2). ¿Y qué dudas tienes sobre el segundo? – WordsWorth

Esto significa que la respuesta proporcionada por mi profesor es incorrecta hmm. – Harminder

parece que la hoja de respuestas contiene errores. – Zohaib

La complejidad tanto de código es O (n * n)

PRIMER

El bucle exterior ejecuta n veces y el bucle interior varía de 0 to n-1 veces

total = 1 + 2 + 3 + 4 ... + n

que si agrega el arithmetic progression es n * (n + 1)/2 es O(n*n)

SEGUNDO

El bucle exterior ejecuta n veces y el bucle interior varía de 0 to n-1/2 veces

así

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

el que si se agrega la progresión aritmética es n * (n + 1)/4 es también O(n*n)

Fuente

2012-01-17 05:28:26

Entonces, si n/2 todavía es igual a o (n)? Pero la iteración para el bucle interno es la mitad del bucle externo que hace alguna diferencia? – Harminder

@ user1085135: 'O (n)' tiene el significado 'linear'. No importa en qué constante se multiplique, lo único que importa es que ** es ** lineal – zerkms

El primer ejemplo es O(n^2), por lo que parece que han cometido un error. Para calcular (informalmente) el segundo ejemplo, podemos hacer n * (n/2) = (n^2)/2 = O(n^2). Si esto no tiene sentido, debe ir y aclarar cuál es el significado de algo que es O(n^k).

Fuente

2012-01-17 05:29:13 Yuushi

primer caso es definitivamente O(n^2)

La segunda es O(n^2), así porque se omite constantes cuando calculamos gran O

Fuente

2012-01-17 05:31:20 zerkms

Su hoja de respuesta es incorrecta, el primer algoritmo es claramente O (n^2).

La notación de Big-Oh es "peor de los casos", por lo que al calcular el valor de Big-Oh, generalmente ignoramos las multiplicaciones/divisiones por constantes.

Dicho esto, su segundo ejemplo también es O (n^2) en el peor de los casos porque, aunque el bucle interno es "solo" 1/2 n, el n es el factor de limitación clara. En la práctica, el segundo algoritmo será menor que O (n^2) operaciones, pero Big-Oh está destinado a ser una medición del "peor caso" (es decir, límite máximo), por lo que se ignora el número exacto de operaciones a favor de centrándose en cómo se comporta el algoritmo cuando n se aproxima al infinito.

Fuente

2012-01-17 05:33:03 debracey

El segundo algoritmo no será inferior a O (n^2), es * precisamente * O (n^2) Sospecho que no tienes muy claro qué significa "O (n^2)" en realidad. Significa que cuando 'n' se acerca al infinito, el tiempo de ejecución aumenta para el algoritmo, para dos valores de' n' es proporcional a la diferencia entre esos 'n' valores al cuadrado. –

No. En la práctica, la complejidad de tiempo real del algoritmo será ligeramente menor que O (n^2). Sin embargo, como Big-Oh es un límite máximo, decimos que es O (n^2). Tiene razón en que el factor 'n/2' está claramente limitado por n, como indiqué en mi respuesta. Hay otras medidas de límite (es decir, Big-Theta) que calculan el factor de límite de forma diferente. – debracey

¿Por qué crees que la complejidad del tiempo real del algoritmo será menor que O (n^2)? Yo afirmo que será * precisamente * O (n^2) porque la complejidad del algoritmo * precisamente * coincide con la * definición * de O (n^2). Si no es * exactamente * O (n^2), entonces nada lo es. * Decimos * que es O (n^2) porque ** es ** O (n^2). Pareces querer hacer esto borroso, confuso e impreciso cuando es absolutamente claro como el cristal. –

Ambos son O(n^2). Tu respuesta es incorrecta O puede haber escrito la pregunta incorrectamente.

Fuente

2012-07-17 06:53:55 Shashwat

Respuesta

Cuestiones relacionadas