0 Daumen
250 Aufrufe

Es geht hier um eine maximale Eingabegröße, welche in t Zeiteinheiten noch bearbeitet werden kann.

Die Komplexität des Algorithmus ist 46 * n * log(n).

Für eine Zeitdauer von 1 Sekunde ist die größte lösbare Eingabelänge 2000.

Nun wurde um die größte lösbare Eingabelänge für 1 Minute zu ermitteln folgendes gerechnet:

t = 1 sek.

60 * ( 46 * nt * log(nt)) = 46 * n60t * log(n60t)

<=> 60 * (2000 log(2000)) = n60t * log(n60t)

<=> n60*t = 82000

Ich verstehe diese Rechnung nicht.

Avatar von

1 Antwort

+1 Daumen

Die Variable \(n_t\) bezeichnet die größte lösbare Eingabelänge, die in t Sekunden gelöst werden kann.

      \(60 \cdot \underbrace{( 46 \cdot n_t \cdot \log(n_t))}_{=1\,\text{Sekunde wegen }t=1} = \underbrace{46 \cdot n_{60t} \cdot \log(n_{60t})}_{=60\,\text{Sekunden}} \)

Für eine Zeitdauer von 1 Sekunde ist die größte lösbare Eingabelänge 2000.

\(n_t = 2000\) einsetzen und Gleichung durch 46 teilen ergibt

        \(60 \cdot ( \cdot 2000 \cdot \log(2000)) = n_{60t} \cdot \log(n_{60t}) \)

Lösen dieser Gleichung mit Computer ergibt

        \(n_{60t}\approx 80726\).

Avatar von 107 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community