3

Saludos a todos ustedes. Tengo un trabajo y es encontrar la complejidad del algoritmo counting sort línea por línea para finalmente encontrar la T(n). La verdad es que ha sido un tema bastante complicado para mí, pero he estado trabajando en ello, así que me gustaría saber si alguien con conocimiento de esto puede decirme si está bien o mal. el pseudocodigo:

                                       cost            repetitions

 for i = 1 to k do                       2                 k+1
    c[i] = 0                             1                  k

 for j = 1 to n do                       2                 n+1
    c[A[j]] = c[A[j]] + 1                2                  n

 for i = 2 to k do                       2                 k+2
    c[i] = c[i] + c[i-1]                 2                  k

 for j = n-1 downto 1 do                 2                 n+1
    B[ c[A[j]]] = A[j]                   1                  n
    c[A[j]] = c[A[j]] - 1                2                  n

Por lo tanto t(n)= 2k+2+k+2n+2+2n+2k+4+2k+2n+2n+2+n+n

T(n)=7k+8n+8

No estoy muy seguro de este análisis, pero es lo mejor que he podido hacer :v. Gracias por cualquier sugerencia.

(Me tomé el atrevimiento de corregir, cuando se hace algoritmia se deben cerrar los ciclos, es solo convención) cuando implementas puedes ofuscar el código con estas sentencias las cuales el compiler de igual forma te cambia.

1 respuesta 1

3

Correción: 1. Perdón por corregir tu código atrevidamente, pues los ciclos no estaban anidados. No cerrarlos explicitamente me estaba perturbando pues por instinto los programadores odian cerrar los for los if y me toca a menudo embellecer código.

Correción: 2. Estaba confundiendo O(n) con T(n), tienes razón y se debe usar la notación T(n) pues O(n) no es una función.

para esta operación se deben multiplicar los ciclos.

por ejemplo:

for i = 1 to n     |  n
 action            |    c0
end                |   delta(n)

                T(n) =    n*(C0) + delta(n) 
                O(n)

i = 1;
while (i <= 1 )    |  n  ______
 action            |     | c0
 i = i + 1         |     |_____ 
end                |   delta(n)

                T(n) =   n*(C0) + delta(n) + ( 1 condición de salida )
                O(n)

El delta es el costo de regresarse en el ciclo, normalmente es 1, es bastante rápido y muchos no los suelen considerar pero soy obsesivo con la T(n) (mal llamada O).

Pero si action = a:

for i = 1 to M     |  m
 action            |    c1
end                |   delta(m)

                     T(m) = m*(C1) + delta(m) 
                     O(n)

Sustituyes:

T(n) = n*( (n*(C1) + delta(n)) ) + delta(n)

O(n²)

Que tengas un buen día, Muchas gracias por hacer que desempolve los libros!

[1] Ref. https://www.quora.com/What-does-T-n-mean-in-relation-to-O-n

4
  • 1
    Para sugerir mejoras en la pregunta, procura añadir comentarios en lugar de editarla. Se puede perder información que otros podrían considerar relevante. :) PD. Buena respuesta!
    – Alfabravo
    Commented el 26 nov. 2019 a las 15:38
  • ok comprendido, Commented el 26 nov. 2019 a las 15:39
  • hola, gracias por responder. Primero disculpa por lo del T(n) la verdad que no entiendo mucho. Ahora, creo que entendí la explicación y efectivamente la complejidad da O(n+k) que es lo que dice la literatura, ahora, a partir de esto me surgen dos preguntas. 1- he estado observando ejemplo de analisis de for y si este es sencillo como lo es los del algoritmo counting sort, el resultado por lo general es 2n+2 ¿por q en este caso no sucede asi? 2- ¿si la complejidad es O(n+k) este vendría siendo mi T(n)? . Gracias, cualquier ayuda es valiosa
    – Felipe
    Commented el 27 nov. 2019 a las 2:53
  • Hola, en el caso del for la condición de fin de ciclo la omití, pero a menudo en los ciclos esa condición siempre se suma, y el delta(n) se suma dentro del Costo general de la función. Detal forma que es correcto el costo (c(n)+1). Por lo tanto tu apreciación está correcta, pero como dicen por allí cuando hay dos rabinos, y una pregunta de dos opciones hay 3 respuestas correctas. Commented el 27 nov. 2019 a las 16:55

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.