Bei welchen Größen schlägt der schnelle Computer mit einem langsamen Algorithmus bei einem schnellen und einem langsamen Computer den langsamen Computer mit einem schnellen Algorithmus?

Die Quelle dieser Frage stammt aus einem Grundstudiengang, der eine Einführung in die Analyse von Algorithmen umfasst. Dies ist keine Hausaufgabe, sondern eine in CLRS gestellte Frage.

Sie haben eine langsame Maschine mit MIPS und eine schnelle Maschine mit MIPS. Sie haben auch zwei Algorithmen derselben Klasse, aber unterschiedliche Laufzeitkomplexitäten: Ein "langsamer" Algorithmus läuft bei während ein "schneller" Algorithmus bei läuft . $x$ $y$ $T(n) = c_1n^2$ $T(n) = c_2n \log n$

Sie führen den langsamen Algorithmus auf der schnellen Maschine und den schnellen Algorithmus auf der langsamen Maschine aus. Was ist der größte Wert von n, so dass die schnelle Maschine, auf der der langsame Algorithmus ausgeführt wird, die langsame Maschine schlägt, auf der der schnelle Algorithmus ausgeführt wird?

Meine bisherige Lösung:

Finden Sie die Menge aller so, dass $n$ wobeieine natürliche Zahl ist.

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

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

n

$n$

Dies ist meine bisherige Arbeit:

{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}\}$

Die einzige Lösung, die mir jetzt in den Sinn kommt, besteht darin, alle Werte von tuckern, bis ich das erste n finde, wo $n$

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

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

hält nicht mehr.

algorithms algorithm-analysis runtime-analysis mathematical-analysis DoggoDougal
quelle

n

$n$

x

$x$

x

$x$

x

$x$

x

$x$

Antworten:

Betrachten Sie Ihre letzte Ungleichung:

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

$C\log n$ $C = \frac{c_2y}{c_1x}$

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

und herauszufinden, welcher Algorithmus in welchem Intervall schneller ist, indem einfach die jeweiligen Funktionswerte zu einem bestimmten Zeitpunkt im jeweiligen Intervall berechnet werden.

$C$

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

$C \geq e \ln 2$ $W_k$ $C$ $\approx 116,74$ $C=17$

Raphael
quelle

Nur um sicher zu gehen: Haben Sie meine Gleichung so interpretiert, dass sie das natürliche log oder log-base-2 hat? Ich sollte klarstellen, dass jede Instanz von log (n) von Basis 2 ist und die Frage entsprechend modifizieren wird.

DoggoDougal

\log = \log_{2}

$\log = \log_2$

\log = \ln

$\log = \ln$

\log

$\log$

2

$2$

\ln 2

$\ln 2$