Laura94
Grünschnabel
Dabei seit: 28.01.2015
Beiträge: 6
|
|
Hey, ich habe eine Tabelle mit verschiedenen Komplexitäten.
Ein Problem braucht für n=1000, 5 Sekunden um bearbeitet zu werden.
Dann soll man jeweils umrechnen, wie lange es für n=2000, 3000 und 10000 braucht.
Bin jetzt grade dabei, das für O(2^n) zu machen und mir ist schon bewusst, dass das praktisch zu den "schlechtesten" Algorithmen zählt, was Zeitkomplexität angeht.
2^1000 entspricht also 5. Wenn ich das umrechen wollte für n=2000 dachte ich, ich gehe so vor:
Die Zahl ist so riesig, dass sich mein Taschenrechner weigert sie darzustellen.
Hab schon damit gerechnet, das was großes rauskommt, allerdings verunsichert mich das Ergebnis etwas, da ich selbst für O(n³) für n=10000 "nur" 5000 rauskriege, wobei das Ergebnis für n=1000 wieder 5 war.
Hoffe mich kann da jemand bestätigen, oder mich auf meinen Fehler hinweisen.
Generell bin ich immer nach obigen Schema vorgegangen also für O(n²) dann zB:
(n²/1000²)*5 = x, dann jeweils für das n 2000, 3000 und 10000 eingesetzt. Vllt rechnet man das auch irgendwie anders aus.
Danke schonmal
|
|
31.01.2015 11:33 |
|
|
Laura94
Grünschnabel
Dabei seit: 28.01.2015
Beiträge: 6
|
|
Hey, vielen Dank
Die Grafik ist echt anschaulich, dh ich gehe mal davon, dass meine Werte auch stimmen
|
|
31.01.2015 11:59 |
|
|
Laura94
Grünschnabel
Dabei seit: 28.01.2015
Beiträge: 6
|
|
Insgesamt sahen meine Werte so aus.
h t t p: / / i.epvpimg.com/vGrsb.jpg
(darf leider keine richtigen Hyperlinks posten, auf Grund nicht ausreichender Beiträge
)
Kommt mir auch recht realistisch vor, bei O(2^n) war ich mir ja erst nicht ganz sicher, aber wenn man sich ihre Grafik nochmal anguckt, scheinen die Werte doch nicht ganz unrealistisch zu sein
|
|
31.01.2015 12:30 |
|
|
|
Wir hatten leider Probleme mit Spam. Aber ich glaube, du darfst beim Editieren deiner Beiträge Links anhängen. Und ich darf sogar direkt verlinken.
Habe die Werte mal nachgerechnet, kriege das selbe Ergebnis.
__________________ Syntax Highlighting fürs Board (Link)
|
|
31.01.2015 12:52 |
|
|
|
|
|