Foros-FIUBA :: Ver tema - Problema de final (wachenchauzer)

FAQ • Buscar • Wiki • Apuntes • Planet • Mapa • Eyeon • Chat
Preferencias • Grupos de Usuarios
Registrarse • Perfil • Entrá para ver tus mensajes privados • Login

Problema de final (wachenchauzer)

Ver tema siguiente
Ver tema anterior

Foros-FIUBA Foros » Académico » Materias » 75. Computación » 75.41 Algoritmos y Programación II » Problema de final (wachenchauzer)

Autor

Mensaje

_MK_
Nivel 2

Registrado: 26 Jul 2011
Mensajes: 10

Carrera: Informática

Publicado: Dom Ago 04, 2013 2:16 am Asunto: Problema de final (wachenchauzer)


tenia un par de dudas con este ejercicio, el enunciado es: 2. La moda de una secuencia de números es el valor que se repite con mayor frecuencia en la secuencia. Escribir un algoritmo O(N log N) para calcular la moda de una secuencia. Justificar el orden. lo unico que se me ocurrio es ordenar el vector con merge sort que es O (n log n) y una vez ordenado recorrerlo linealmente e ir guardando cual numero se repetio la mayor cantidad de veces, pero dudo que este bien. trate de plantearlo por dividir y conquistar pero no encontre forma de hacerlo ya que no veo la forma de dividirlo en subproblemas, y no se me ocurrio ninguna otra manera de encararlo. cualquier sugerencia me vendria bien, gracias

Sebastian Santisi
Administrador Técnico

Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451

Publicado: Dom Ago 04, 2013 9:42 am Asunto: (Sin Asunto)


Por dividir y conquista si es que puede sacarse no creo que salga fácil ni un poquito, así que no te quemes el bocho. Para mí lo que hiciste está bien; te pedían un orden y tu algoritmo lo resuelve en ese orden (con la desventaja de usar un O(n) en memoria porque por prolijidad deberías duplicar el vector para no romperlo). También hubieras cumplido con el orden si hacías algo más eficiente onda un hash con el número como clave y la cantidad de apariciones como valor. Cargás el hash en una pasada, y en una pasada por el hash encontrás la clave con más ocurrencias. Orden total O(n).

_________________

$[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]$ $[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]$

_MK_
Nivel 2

Registrado: 26 Jul 2011
Mensajes: 10

Carrera: Informática

Publicado: Dom Ago 04, 2013 4:21 pm Asunto: (Sin Asunto)


Ah barbaro entonces, gracias por la respuesta Sebastian.

Foros-FIUBA Foros » Académico » Materias » 75. Computación » 75.41 Algoritmos y Programación II » Problema de final (wachenchauzer)

Cambiar a:

Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro

Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker
365 Attacks blocked.

Foros-FIUBA está hosteado en Neolo.com Cloud Hosting

[ Tiempo: 0.3149s ][ Pedidos: 20 (0.2516s) ]