Qual é a complexidade de uma ordenação externa multi-way de 2 fases usando quick sort (nlogn) como classificação interna.
Respostas:
0 para resposta № 1Não é um especialista aqui, mas ...
Se bem entendi, o que você descreve como fases são o número de passes seu algoritmo fará a entrada, certo? Nesse caso, uma aproximação de tempo de execução seria o número de passagens (2 no seu caso) * o tempo necessário para ler e gravar toda a entrada no dispositivo externo.
Ao avaliar a complexidade de tais algoritmos,É difícil colocá-lo em termos usuais de tempo de execução. Existem muitos aspectos que podem influenciar o resultado (acesso sequencial / não seqüencial, tecnologia, etc). A abordagem comum é fornecer complexidade em termos de passes, que considera o número de dispositivos usados, o número de itens na entrada e o número de itens que podem caber na memória.
O ponto é que o algoritmo de ordenação é dominado pelas operações IO. A classificação rápida interna deve estar ok (embora seja o pior cenário quadrático).
Além disso, eu não tenho certeza se você contou a distribuição inicial. Este também é um passe.