Laufzeitkomplexität

[Denden87]

Einen schönen guten Tag wünsche ich euch allen,

ich habe noch eine offene Frage, wo ich mir nicht so sicher bin.

Ich soll die Laufzeitkomplexität herausfinden.

void func( int n ) {

int h = 1;

while ( h <= n ) {

c= c + h;

h= h * 2; }}

Würde dann hier T(n) = 1*n+3 also O(n) rauskommen?

[carstenj]

Hi,

deine Rechnung verstehe ich nicht ganz, aber meiner Meinung nach ist es sogar O(log_n). N wäre es, wenn n=10 ist und es 10 Berechnungen gäbe, was aber nicht der Fall ist.

Die Variable "c" ist egal, aber da "h" ja bei jedem Durchgang verdoppelt wird, verringert sich dadurch die Laufzeit, weil die Bedingung schneller erfüllt ist.

[Denden87]

was wäre hier die T(O)? :-/

[mfk'); DROP TABLE Users;--]

Was meinst du mit T? Versuchst du, das Master-Theorem anzuwenden? Hast du bemerkt, dass die Funktion nicht rekursiv ist?

[Denden87]

T(n) ist Aufwandfunktion

[Denden87]

Hi,

deine Rechnung verstehe ich nicht ganz, aber meiner Meinung nach ist es sogar O(log_n). N wäre es, wenn n=10 ist und es 10 Berechnungen gäbe, was aber nicht der Fall ist.

Die Variable "c" ist egal, aber da "h" ja bei jedem Durchgang verdoppelt wird, verringert sich dadurch die Laufzeit, weil die Bedingung schneller erfüllt ist.

Also würde dann T(n)=1+2log(n) ?

[carstenj]

Hi,

so würde ich das sehen: Du hast eine Operation die nur einmal ausgeführt wird (h = 1) , und zwei die eben solange ausgeführt werden, wie die Bedingung erfüllt ist.

Also quasi 2 * ((((n/2)/2)/2)....), was eben der Logarithmus zur Basis 2 von n ist.