Autor Tema: Quicksort

0 Usuarios y 1 Visitante están viendo este tema.

03 Diciembre, 2012, 08:54 am
Leído 1532 veces

cayitounico

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 303
  • Karma: +0/-0
  • Sexo: Masculino
  • No soy un genio, pero estudiando !aprendo!
Probar que el tiempo de ejecución de Quicksort es de orden \( n\log(n) \) cuando todos los elementos del arreglo A tienen el mismo valor.

No logro entender como seria la ecuación del tiempo de complejidad.
R.E.Q.A.

07 Diciembre, 2012, 04:11 am
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Tendrías que detallar la implementación del algoritmo, pues la que yo conozco es de orden \( n^2 \) cuando todos los elementos son iguales.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print