Intro zu Algorithmen (Kapitel 1-1)

Question

Gerade dieses Buch zum Spaß lesen, das ist keine Hausaufgabe.

Jedoch bin ich bereits verwirrten auf der ersten Hauptbelegung:

1-1 Vergleich der Laufzeiten

Für jede Funktion f (n) und der Zeit t in der folgenden Tabelle, die bestimmen, größte Größe n eines Problems, das zur Zeit t gelöst werden kann, unter der Annahme, dass der Algorithmus zur Lösung des Problems f (n) Mikrosekunden benötigt.

Was bedeutet das überhaupt?

Die nächste Tabelle zeigt eine Reihe von Malen entlang einer Achse (1 Sekunde, 1 Minute, 1 Stunde, usw.), und die andere Achse zeigt verschiedene f (n) wie lg n, sqrt (n), n, usw.

Ich bin nicht sicher, wie man die Matrix ausfüllt, weil ich die Frage nicht verstehen kann. Wenn also f (n) = lg n ist, wird nach dem größten n gefragt, das zum Beispiel in 1 Sekunde gelöst werden kann, aber das Problem braucht f (n) = lg n Mikrosekunden, um zu lösen? Was bedeutet dieser letzte Teil überhaupt? Ich weiß nicht einmal, wie ich die Gleichungen/Verhältnisse aufstellen soll, um dieses Problem zu lösen, weil ich buchstäblich nicht einmal die Bedeutung der Frage zusammenstellen kann.

Mein Aufhängen ist über den Satz "angenommen, dass der Algorithmus zur Lösung des Problems f (n) Mikrosekunden dauert", weil ich nicht weiß, worauf sich das bezieht. Die Zeit für was Algorithmus zu lösen was Problem dauert f (n) Mikrosekunden? Wenn ich also f (100) anrufe, dauert es 100 Mikrosekunden. Also muss ich ein paar n finden, wobei f (n) = lg n Mikrosekunden = 1 Sekunde ist?

Bedeutet dies lg n Mikrosekunden = 1 Sekunde wenn lg n Mikrosekunden = 10^6 Mikrosekunden, also n = 2^(10^6)?

Answer 1

Für jede Zeit T und jede Funktion f(n), können Sie die maximale ganze Zahl n so dass f(n) <= T

Zum Beispiel zu finden sind erforderlich, f(n) = n^2, T=1Sec = 1000 ms:

n^2 <= 1000 
n <= sqrt(1000) 
n <= ~31.63 <- not an integer 
n <= 31 

jede Funktion f(n) gegeben, und einige Zeit T, müssen Sie ebenfalls den Maximalwert n finden und die Tabelle ausfüllen.