Aufg. 1.1 Quiz

kriz
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 26. Nov 2004 23:38

Aufg. 1.1 Quiz

Beitrag von kriz »

Hallo,
sind hier grade am wiederholen und fragen uns, warum beim quiz sofern ich alle notationen richtig geschnackelt habe, 2^n in einer anderen, komplexitätsklasse als 2^n/2 liegt? denn ob ich 2^n oder 1,41^n habe, ändert für mich nicht das grobe verhalten?!

thx

TimN
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 19. Feb 2005 12:30

Beitrag von TimN »

Naja, macht doch mal eine Grenzwertbetrachtung von 2^n/(2^(n/2)) für n gegen unendlich und überlegt euch dann, was euer Ergebnis bedeutet.

kriz
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 26. Nov 2004 23:38

Beitrag von kriz »

ich sehe zwischen 2^n und 1,4^n keinen signifikanten unteschied, sodass ich behaupten koennte, das es keine exponentielle größe mehr ist ^^

am rande, wenn jmd einen ansatz fuer Z 3.7 Minimaler Spannbaum - Kruskal hat, wäre ich auch um den tipp dankbar

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

2^n = 2^(n/2) * 2^(n/2) = (2^(n/2))^2
Klar, oder? Das ist ganz bestimmt nicht in O(2^(n/2)). Oder wie willst du entsprechende konstante Faktoren dafür finden?

Oder für deine Umschreibung:

2^n = e^(n*ln2) = (e^n)^ln2, 1.4^n = e^(n*ln1.4) = (e^n)^ln1.4
Und wieder hast du andere Faktoren im EXPONENTEN, was du niemals mit einem konstanten Faktor davor kompensieren kannst, ergo wachsen die Funktionen nicht gleich schnell.

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Beitrag von mantra »

Ich ignoriere auch immer gut gemeinte Tipps.. :shock:
kriz hat geschrieben:ich sehe zwischen 2^n und 1,4^n keinen signifikanten unteschied, sodass ich behaupten koennte, das es keine exponentielle größe mehr ist ^^
Keiner behauptet, dass 1,4^n nicht exponentiell wächst.

kriz
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 26. Nov 2004 23:38

Beitrag von kriz »

also ich denke nicht, dass meine frage so missverständlich formuliert war...

mal n tutor nervem, thx anyway

TimN
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 19. Feb 2005 12:30

Beitrag von TimN »

Ähm bin schon genervt(ne, war nur spaß ;-))

Macht doch wirklich mal ne Grenzwertbetrachtung, macht Spaß und BEANTWORTET DIE FRAGE!!!

Thank you and good night...

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Beitrag von mantra »

kriz hat geschrieben:also ich denke nicht, dass meine frage so missverständlich formuliert war...

mal n tutor nervem, thx anyway
Nein, alles unmissverständlich. Du hast die Notationen nicht richtig geschnackelt.

Antworten

Zurück zu „Archiv“