2

Dúvida:

Para ordenar arrays com heapsort, costuma-se simular neles árvores com até dois filhos por pai, não mais. Minha dúvida é se há estudos, implementações, experimentos, relatórios, dados acessíveis que investigam o desempenho do heapsort em arrays simulando árvores com números maiores de filhos por pai.

Detalhes:

Eu implementei a ordenação de array com heapsort usando o máximo de dois filhos por pai. Com as noções de complexidade de código que tenho, me pareceu que o número de comparações de uma interação do heapsort (definição do último elemento do subarray atual) fica, no pior caso, em torno de 2*log2(n), pois são duas comparações por nível de profundidade e a profundidade fica em torno de log2(n). Mas e se eu "adotasse mais filhos"?

Pensando nisso, suponho que possamos adaptar o código para mais de dois filhos adicionando, para cada filho adicional, uma comparação por nível de profundidade. Aumenta as comparações por profundidade, mas a profundidade diminui, assim talvez realizando menos comparações. A fórmula que encontrei para estimar as comparações por interação dependendo do número F de filhos é F*logF(n).

Se eu estiver certo, matematicamente o ideal seria F = e ~ 2.71828, mas não dá. Aumentar de dois filhos para três filhos diminuiria o número de comparações (-5,36% em F=3). Aumentar de dois para quatro filhos, conservaria (0,00% em F=4). Aumentar de dois para cinco filhos ou mais aumentariam as comparações (+7,67% se F=5). Enfim, matematicamente é assim, mas como é o desempenho na prática? Já se testou isso? Há dados conhecidos?

12
  • 1
    A grosso modo, a adoção de um filho a mais faria com que se multiplicasse por um termo constante a complexidade assintótica, portanto estaria dentro da mesma classe de complexidade temporal. Tempo de execução real, porém, já não sei. Commented 22/09/2017 às 21:19
  • Exatamente. Assintoticamente, nada muda. Quero saber como é na prática. Talvez eu mesmo tenha que experimentar. Não acho nada na internet.
    – RHER WOLF
    Commented 22/09/2017 às 21:40
  • eu fiz um repositório em Java para testar algoritmos de ordenação, quer incluir lá? Commented 22/09/2017 às 21:41
  • 1
    Certo. Na verdade, implementei em C++, mas posso converter para java se eu conseguir implementar direito.
    – RHER WOLF
    Commented 22/09/2017 às 21:53
  • 1
    O(log3(n)) e O(log2(n)) são assintoticamente equivalentes. Que de certa forma estou a dizer o que o @JeffersonQuesado disse mas de outra forma.
    – Isac
    Commented 22/09/2017 às 23:24

0

Você deve fazer log-in para responder a esta pergunta.

Pesquise outras perguntas com a tag .