Komplexität O(2^n) |
| 31.01.2015, 11:33 | Auf diesen Beitrag antworten » | ||
| Laura94 | Komplexität O(2^n) 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:54 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Exponentielles Wachstum ist "schlecht". Ich habe dir mal ein Bild mit linearem, quadratischem, kubischem und exponentiellem Wachstum erstellt. Alles eine Frage des richtigen Rechners, als Zahlenwerte erhalte ich: n=2000: 535754303593133660474212524530000905280702405852766803721875194185175525562 468061246599189407847929063797336458776573412593572642846157021799228878734 928740196728388741211549271053730253118557093897709107652323749179097063369 938377958277197303853145728559823884327108383021491582631219341860283403468 80 = 5.3575430359313366047421252453000090505 E301 n=3000: 574065347637127262116416600588840992011158851044347600238821368412883130696 185156928329743158253134959222982319493731386723559480431527665712965678083 326592695649945726561400003443895741200224357144634950317431223908077318231 941819736585130202331769854524982790811994044723148028116558247680821109851 663406720844544922292528011897424039570294504673882502145013583533129152610 040661181406458806339416586032994976982090635108899292020210799265916257704 447169510459602774788917948360195800409786083152913776902127918630077641743 932097160272544576378919413125877177644004114213854089827268810924255745146 880 = 5.7406534763712726211641660058884099151 E602 n = 10000: 930959911801223435025823473721632903109340440810082075080654877666590696173 737984868958442951962989844141188362622525464276009925349915468339144555287 282272948904074195334739884044051582087431307157448180875746209677600372459 553386535539791299573901419853107805437356788730585742194507265732763815101 118441921831413163242102302984725146154606239788377050742105219014696423558 696604823306209121734472658221527701556094884997097191126605534537841105162 332690183581699175630195032573275481676819113115285543576545238002915517231 935611799771683720063685660653967800147117617777843325597087260377854616626 073634856323076199330636307697165128383459927106904327568227239139760269462 657579560344724523412382638496935542362563144587321130567093266476194764748 725612647140154796166559273715928917011053649746653821443275017554174906269 434274102055474633503922447460652362219616140015242016473277931010809411231 987685781695233238046971166510953007310547566260834385772273699111154611192 727126405054634997520652954874451742561782595701731062887127046982683419099 546471334881617248877897961391184207695704164307970543843584071351784739165 319764083596716552771815238294350674252771783875895394558858830076370867151 994541448870184518146358313730446572689237951618213141854951426912916761342 610515131708649231426195919073786291509193237787121111860062804926184775054 267804919148422942770165702576668252014828712926341308499382534489485255334 288352378671984950235808309243765608711804063124153024672706099851162608523 142606624642923076987656989121337501701481412060580437964304309167503108525 856130097565368541508815674908334964579588333934208676933452756917777499731 318740671360700487819752241358354692077928013131652135130443370405143579016 151041694445723275953599334736660057185859069221830297455733117367471455361 224522622228987660021847084630850840828074181102585266497140576288426854834 883708063626369218742896955109923418249134015578630896429615033647724592457 115463230995850421185505118294298339671246371955807682855660371607993997950 550581653038272284313265599404685453806165741735916922979309038740108946445 266558301675020073558109113964366408972661818211023753578213567648611137906 339093868018386660427469229494820825599539396329354702574978503941437687434 090221234354564060323523651562950921530452104311076499250308755401371216077 572302924485641104065874801204095904203205316087632585653118896978285203217 701172738314233604534364946567216562145593758037633797149161549243995083121 701734456314058694221577460737331574518320491902235754782446713019565240035 316184729070625742526468021082432888609936991544786193755897369786076147009 815611072955450605420280722753856827829444668186783400195603462606193228487 1578746880 = 9.3095991180122343502582347372163290223 E2709 |
||
| 31.01.2015, 11:59 | Auf diesen Beitrag antworten » | ||
| Laura94 | Hey, vielen Dank 
Die Grafik ist echt anschaulich, dh ich gehe mal davon, dass meine Werte auch stimmen 
|
||
| 31.01.2015, 12:01 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl |
der Wert stimmt schonmal. |
||
| Anzeige | |||
|
|
|||
| 31.01.2015, 12:30 | Auf diesen Beitrag antworten » | ||
| Laura94 | 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:52 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | 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. |
||
|
|
