Questão 6 da prova do ano passado

[Ricardo Correa]

Oi Pessoal,

Alguem resolveu a questão 6 da prova do ano passado?
Era só para explicar a diferença da complexidade do radix-sort (theta(d(n+k))) e a do insertion-sort (O(n²)) ?
Ficaria algo do tipo.... para um numero de bits a serem comparados que não implique um d (numero de digitos a serem comparados) maior que n, teremos um resultado no radix muito melhor que o insertion-sort.
Acredito que não tenha entendido direito.

valeu,
Ricardo.

[Carla Négri]

Na verdade era pra comparar um algoritmo que usava radix + insertion com só o radix..
Minha resposta foi assim:

algoritmo 1: usar radix em k dígitos dá um tempo theta(nk) (porque o counting vai ser theta(n+2) = theta(n))
usar o insertion sobre o resultado disso é theta(n 2^(d-k)) porque se as entradas estão ordenadas nos k primeiros dígitos, o deslocamento máximo que o insertion faz na hora de ordenar é de 2^(d-k) elementos (a entrada está quase ordenada)
(o exercício 2-1 letra (a) mostra mais ou menos o porque desse deslocamento influenciar no tempo do insertion)
Tempo_alg1 = theta(nk + n 2^(d-k)) = theta(n(k + 2^(d-k))

algoritmo 2: usar apenas o radix dá tempo theta(nd).
Tempo_alg2 = theta(nd)

Comparando Tempo_alg1 com Tempo_alg2, o algoritmo 1 supera o algoritmo 2 se d > k + 2^(d-k)

E aí eu parei aqui =)

--
Carla Négri Lintzmayer (@carlanegri)
Mestranda em Ciência da Computação pela Universidade Estadual de Campinas
Bacharel em Ciência da Computação pela Universidade Estadual de Maringá

"Política é para o presente, mas uma equação é para a eternidade." (Albert Einstein)

[João Paulo Pereira Zanetti]

O que eu acho que dava pra dizer também é que, no melhor caso, os k
bits mais significativos de cada elemento são distintos e o radix já
ordena o vetor, e aí o insertion sort é linear, dando theta(nk).

O pior caso seria o contrário, todo mundo tem os k dígitos mais
significativos iguais. Aí o radix não faz nada e o insertion sort tem
que ordenar tudo, dando theta(n^2).

Note que d > k + 2^(d-k) nunca vai ser verdade.

2012/5/13 Carla Négri <carla...@gmail.com>: