Dado um computador rápido e lento, em que tamanhos o computador rápido executando um algoritmo lento supera o computador lento executando um algoritmo rápido?

8

A fonte dessa pergunta vem de um curso de graduação que estou cursando, que abrange uma introdução à análise de algoritmos. Isso não é para trabalhos de casa, mas para uma pergunta feita no CLRS.

Você tem uma máquina lenta rodando em x MIPS e uma máquina rápida rodando em yMIPS. Você também tem dois algoritmos da mesma classe, mas diferentes complexidades de tempo de execução: um algoritmo "lento" é executado emT(n)=c1n2 considerando que um algoritmo "rápido" é executado em T(n)=c2nlogn.

Você executa o algoritmo lento na máquina rápida e o algoritmo rápido na máquina lenta. Qual é o maior valor de n de modo que a máquina rápida que executa o algoritmo lento supera a máquina lenta que executa o algoritmo rápido?

Minha solução até agora:

Encontre o conjunto de todos n de tal modo que

c2nlognx>c1n2y
Onde n é um número natural.

Este é o meu trabalho até agora:

{n:c2nlog2nx>c1n2y,nN}={n:n<c2yc1xlog2n,nN}

A única solução que vem à mente agora é conectar todos os valores de n até encontrar o primeiro n onde

n<c2yc1xlog(n)

não é mais válido.

DoggoDougal
fonte
3
Isso é realmente mais uma questão de matemática do que de ciência da computação. Se você substituirn com x então você tem uma equação transcendental sobre os reais, que você não pode realmente reduzir para uma solução de forma fechada para x. Depois de encontrar umx, sua resposta é xarredondado para o número inteiro mais próximo. Em outras palavras, "plug-n-chug" ou "palpite e cheque" são tão bons quanto você pode fazer no caso geral. Isso geralmente se manifesta como métodos gráficos ou numéricos.
precisa saber é o seguinte

Respostas:

2

Considere sua última desigualdade:

n<c2yc1xlog(n)

Agora, Clogn com C=c2yc1xé uma função côncava . Portanto, existem no máximo duas interseções e apenas uma delas é interessante para você; isto é, resolver

n=Clog(n)

e descubra qual algoritmo é mais rápido em qual intervalo, simplesmente calculando os respectivos valores de função em algum momento do respectivo intervalo.

É verdade que resolver explicitamente essa igualdade é difícil / impossível. Para algunsC, álgebra computacional fornece uma expressão em uma função conhecida; interessante interseção (real) acaba sendo

n=eW1(ln2C)

E se Celn2com Wka continuação analítica da função de log do produto . Esta função não possui um bom formulário fechado, mas pode ser avaliada numericamente por um determinado período.C; por exemplo, você obtém116,74 para C=17.

Rafael
fonte
Apenas certificando-se: você interpretou minha equação como tendo o log natural ou log-base-2? Devo esclarecer que todas as instâncias do log (n) são da base 2 e modificarão a questão adequadamente.
DoggoDougal 19/09/12
No CS, geralmente usamos log=log2, enquanto os matemáticos assumem log=ln. Portanto, onde eu usolog é para basear 2, exceções são observadas. É aqui (provavelmente) ondeln2vem no resultado.
Raphael