Étant donné un ordinateur rapide et lent, à quelles tailles l'ordinateur rapide exécutant un algorithme lent bat-il l'ordinateur lent exécutant un algorithme rapide?

La source de cette question provient d'un cours de premier cycle que je suis, qui couvre une introduction à l'analyse des algorithmes. Ce n'est pas pour les devoirs, mais plutôt une question posée dans CLRS.

Vous avez une machine lente fonctionnant à $x$ MIPS, et une machine rapide fonctionnant à $y$ MIPS. Vous avez également deux algorithmes de la même classe, mais des complexités de temps d'exécution différentes: un algorithme "lent" s'exécute à $T(n) = c_1n^2$ alors qu'un algorithme "rapide" fonctionne à $T(n) = c_2n \log n$ .

Vous exécutez l'algorithme lent sur la machine rapide et l'algorithme rapide sur la machine lente. Quelle est la plus grande valeur de n telle que la machine rapide exécutant l'algorithme lent bat la machine lente exécutant l'algorithme rapide?

Ma solution jusqu'à présent:

Trouvez l'ensemble de tous $n$ tel 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}$ où

n

$n$ est un nombre naturel.

Voici mon travail jusqu'à présent:

{n : \frac{c_{2} n {Journal}_{2} n}{X} > \frac{c_{1} n^{2}}{y}, n \in N} = {n : n < \frac{c_{2} y}{c_{1} X} {Journal}_{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}\}$

La seule solution qui me vient à l'esprit maintenant est de brancher et de brancher toutes les valeurs de $n$ jusqu'à ce que je trouve le premier n où

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

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

ne tient plus.

algorithms algorithm-analysis runtime-analysis mathematical-analysis DoggoDougal
la source

C'est vraiment plus une question de mathématiques qu'une question d'informatique. Si vous remplacez

n

$n$ avec

x

$x$ alors vous avez une équation transcendantale sur les réels, que vous ne pouvez pas vraiment réduire à une solution de forme fermée pour

x

$x$ . Une fois que vous avez trouvé un

x

$x$ , votre réponse est

x

$x$ arrondi à l'entier le plus proche. En d'autres termes, "plug-n-chug" ou "guess-and-check" est à peu près aussi bon que vous pouvez le faire dans le cas général. Cela se manifeste généralement sous forme de méthodes graphiques ou numériques.

Patrick87

Réponses:

Considérez votre dernière inégalité:

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

Maintenant, $C\log n$ avec $C = \frac{c_2y}{c_1x}$ est une fonction concave . Par conséquent, il y a au plus deux intersections, et une seule d'entre elles vous intéresse; c'est-à-dire, résoudre

$\qquad \displaystyle n = C\log(n)$

et découvrir quel algorithme est plus rapide dans quel intervalle en calculant simplement les valeurs de fonction respectives à un certain point dans l'intervalle respectif.

Il est vrai que résoudre cette égalité de manière explicite est difficile / impossible. Pour certains fixes $C$ , l'algèbre informatique vous donne une expression dans une fonction bien connue; intéressante (réelle) intersection se révèle être à

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

si $C \geq e \ln 2$ , avec $W_k$ la poursuite analytique de la fonction de journal de produit . Cette fonction n'a pas une belle forme fermée, mais elle peut être évaluée numériquement pour $C$ ; par exemple, vous obtenez $\approx 116,74$ pour $C=17$ .

Raphael
la source

Juste pour m'assurer: avez-vous interprété mon équation comme ayant le logarithme naturel ou log-base-2? Je dois préciser que chaque instance de log (n) est de base 2 et modifiera la question de manière appropriée.

DoggoDougal

Dans CS, nous utilisons généralement

\log = \log_{2}

$\log = \log_2$ , alors que les mathématiciens supposent

\log = \ln

$\log = \ln$ . Par conséquent, là où j'utilise

\log

$\log$ c'est pour baser

2

$2$ , des exceptions sont notées. C'est (probablement) où

\ln 2

$\ln 2$ vient du résultat.

Raphael