Big O Notation Zeit Frage

Question

Wir haben drei Funktionen mit großen o Bezeichnungen:

Func A: O(n) 
Func B: O(n^2) 
Func C: O(2^n) 

Wenn diese Funktionen nicht n proccesses in 10 Sekunden, wie Bedarf viel Zeit für die einzelnen Funktionen 2 * n Prozesse Proccess? Auch wenn du erklärst, warum ich glücklich sein werde.

Danke

Answer 1

Eigentlich kann man wirklich nicht mit nur einem Datenpunkt sagen. Eine simple Antwort für die erste wäre beispielsweise "doppelt so lang", 20 Sekunden, da O (n) bedeutet, dass die Zeitkomplexität direkt proportional zum Eingangsparameter ansteigt.

Dies berücksichtigt jedoch nicht, dass das Big-O normalerweise vereinfacht wird, um nur den höchsten Effekt zu zeigen. Die tatsächliche Zeit kann durchaus proportional zu n plus eine Konstante 5 sein - mit anderen Worten, es gibt eine konstante 5-Sekunden-Setup-Zeit, die nicht von n überhaupt abhängt, dann eine halbe Sekunde pro n danach.

Das würde bedeuten, die Zeit würde 15 Sekunden statt 20 sein. Und für die anderen genannten Fällen ist es noch schlimmer, da O (n) kann tatsächlich proportional zu n^2 + 52n + 7 was bedeutet, dass Sie drei Datenpunkte benötigen würde, vorausgesetzt, Sie sogar wissen alle Komponenten der Gleichung. Es könnte sogar etwas sein scheußlich wie:

    1  12 
n^2 + 52*n + 7 + --- + ------ 
        n 47*n^5 

die noch technisch O (n) sein würde.

Wenn sie sind simplistic Gleichung (die für Hausaufgaben wahrscheinlich ist), dann müssen Sie nur die Gleichungen zusammensetzen und dann 2n anschließen, wo immer Sie n haben, dann wiederholen Sie die Gleichung in Bezug auf das Original:

Complexity Equation  Double N  Time Multiplier 
---------- -------- ------------- --------------- 
O(n)  t = n  t = 2n    2 
O(n^2)  t = n^2 t = (2n)^2 
         = 4 * n^2   4 
O(2^n)  t = 2^n t = 2^(2n) 
         = 2^n * 2^n  2^n 
              (i.e., depends on 
                original n) 

So., die Antworten, die ich hätte gegeben hätte:

• (A) 20 Sekunden;
• (B) 40 Sekunden; und
• (C) 10 x 2 ⁿ Sekunden.

Answer 2

Hier ein Tipp

Func A ist Ihre Basis Maßnahme, die 1 Zeiteinheit in Anspruch nimmt. In diesem Problem beträgt Ihre Zeiteinheit 10 Sekunden. Also O(2*n) = 2*O(n) = 2 * Units = 2 * 10 sec = 20 sec.

Stecken Sie einfach 2*n in die n^2 und 2^n Funktionen

O((2*n)^2) = O(2^2 * n^2) = O(4 * n^2) 
    O(2^(2*n)) = O((2^2)^n) = O(4^n) 

Jetzt nur herausfinden, zu bekommen, wie viele Zeiteinheiten jeweils und um 10 Sekunden zu multiplizieren.

Answer 3

A: 2-mal so viel

B: 4-mal so viel

C: 2^n-mal so viel

?

Zeit ist abhängig von n jetzt

gegeben Zeit beträgt 10 Sekunden und n auch 10, das 20, 40 und 1024 Sekunden jeweils :)

aber wenn n 1 macht, wird es 20 sein, 40 und 40 ...

Answer 4

EDIT: C 10 * 2^n ist, machte ich einen Fehler in meiner Antwort. Ich werde es unten lassen, aber hier ist der Fehler:

Die echte Formel enthält die Verarbeitungsrate, die ich in meiner ursprünglichen Antwort weggelassen. Die Verarbeitungsrate fällt weg in den ersten beiden, aber es nicht in C.

2^n/p=10 (where p is the processing rate of units/second) 
2^n=10*p 
y=2^(n*2)/p 
y=(2^n)^2/p 
y=(10*p)^2/p 
y=100*p^2/p 
y=100*p (so we need to know the processing rate. If we know n, then we know the processing rate) 

Die Einheiten sind oben in Ordnung, wie wir Sekunden^2/s = Sekunden haben.

Original-Antwort:

A: 20 B: 40 C: 100 Die bestehenden Antworten bereits erklären A und B die C Gleichung betrifft, wenn meine Mathematik mich richtig dienen ....

Teil 1: Was

2^n=10 
log(2^n)=log(10) 
n*log(2)=log(10) 
n=log(10)/log(2) 

Teil n gleich tut 2: Nun

n mit 2 * n ersetzen

x = 2^(2*n) 
x = 2^(2*log(10)/log(2)) 
x = 100 (thanks excel: =2^(2*LOG(10)/LOG(2))) 

Noch habe ich logarithms in 6 Jahren nicht verwendet, also bitte verzeihen Sie, wenn ich falsch liege.

BEARBEITEN: Einen einfacheren Weg gefunden.

Given t is orginal time, and y is the new time. 
t=2^n 
y=2^(n*2) 
y=(2^n)^2 
y=t^2 
y=10^2 
y=100