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?

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 $y$ MIPS. Você também tem dois algoritmos da mesma classe, mas diferentes complexidades de tempo de execução: um algoritmo "lento" é executado em $T(n) = c_1n^2$ considerando que um algoritmo "rápido" é executado em $T(n) = c_2n \log n$ .

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

\frac{c_{2} n \log n}{x} > \frac{c_{1} n^{2}}{y}

$\frac{c_2n\log n}{x} > \frac{c_1n^2}{y}$ Onde

n

$n$ é um número natural.

Este é o meu trabalho até agora:

{n : \frac{c_{2} n \log_{2} n}{x} > \frac{c_{1} n^{2}}{y}, n \in N} = {n : n < \frac{c_{2} y}{c_{1} x} \log_{2} n, n \in N}

$\{n : \frac{c_2 n \log_2 n}{x} > \frac{c_1 n^2}{y}, n \in \mathbb{N}\} = \{n : n < \frac{c_2 y}{c_1 x} \log_2 n, n \in \mathbb{N}\}$

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

n < \frac{c_{2} y}{c_{1} x} \log (n)

$n < \frac{c_2y}{c_1x}\log(n)$

não é mais válido.

algorithms algorithm-analysis runtime-analysis mathematical-analysis DoggoDougal
fonte

Isso é realmente mais uma questão de matemática do que de ciência da computação. Se você substituir

n

$n$ com

x

$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

$x$ . Depois de encontrar um

x

$x$ , sua resposta é

x

$x$ arredondado 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:

Considere sua última desigualdade:

$\qquad \displaystyle n < \frac{c_2y}{c_1x}\log(n)$

Agora, $C\log n$ com $C = \frac{c_2y}{c_1x}$ é uma função côncava . Portanto, existem no máximo duas interseções e apenas uma delas é interessante para você; isto é, resolver

$\qquad \displaystyle n = C\log(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 alguns $C$ , álgebra computacional fornece uma expressão em uma função conhecida; interessante interseção (real) acaba sendo

$\qquad \displaystyle n = e^{-W_{-1}(-\frac{\ln 2}{C})}$

E se $C \geq e \ln 2$ com $W_k$ a 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ém $\approx 116,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 = \log_{2}

$\log = \log_2$ , enquanto os matemáticos assumem

\log = \ln

$\log = \ln$ . Portanto, onde eu uso

\log

$\log$ é para basear

2

$2$ , exceções são observadas. É aqui (provavelmente) onde

\ln 2

$\ln 2$ vem no resultado.

Raphael