Komplexität > Eine Funktion N -> N soll weder in O(n) noch in Omega(n) liegen |
Tai
Grünschnabel
Dabei seit: 27.04.2011
Beiträge: 5
|
|
Komplexität > Eine Funktion N -> N soll weder in O(n) noch in Omega(n) liegen |
|
Meine Frage:
Ich suche eine Funktion f : N -> N die weder in O(n) noch in Omega(n) ist.
Meine Ideen:
Ich habe leider überhaupt kein Ansatz dafür
|
|
27.04.2011 19:00 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Vorschlag: Was Alternierendes?
VG,
Karlito
|
|
27.04.2011 22:45 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
28.04.2011 08:30 |
|
|
Tai
Grünschnabel
Dabei seit: 27.04.2011
Beiträge: 5
|
|
Hallo,
ich überlege gerade so, wenn ich jetzt 2 verschiede Funktionen (z.B. f1 und f2) habe die Ausgeführt werden sollen von der Funktion von der ich die Komplexitätsklasse haben möchte, dann hab ich doch aber die Komplexitätsklasse von groß O(max(f1, f2)) und Omega(min(f1,f2)).
Dein Tipp mit den Brüchen bringt mich irgendwie nicht viel weiter.
Das einzige was mir einfällt, sind mir ein paar Gedanken, die aber laut meinen Verständniss nicht viel mit Komplexität haben.
Ich weiß vorallem nicht worauf es hinauslaufen soll.
Exceptions? z.B. 0/0
Etwas unkalkulierbares? Darüber kann ich mir garnichts vorsellen.
Sockets/Connetctions? Das dürfte eigentlich nicht die Komplexität beeinträchtigen.
Stetigkeit?
n = Input
l = Input länge
i = counter
z.B.
G1:
code: |
1:
2:
3:
4:
5:
6:
7:
|
Für jedes Element e
wenn i % 2 == 0
rufe f1 mit e auf
sonst
rufe f2 mit e auf
|
|
G2:
code: |
1:
2:
3:
4:
5:
6:
7:
|
Für jedes Element e
wenn 10/e > 0
rufe f1 mit e auf
sonst
rufe f2 mit e auf
|
|
G3:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
|
Wenn l > 50
Wenn i < 25
rufe f1 auf
Sonst
rufe f2 auf
sonst
mach nichts
|
|
Danke für deine Hilfe
|
|
02.05.2011 03:07 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
02.05.2011 07:30 |
|
|
Tai
Grünschnabel
Dabei seit: 27.04.2011
Beiträge: 5
|
|
Ich habe hier einen kleine Auszug aus dem Skript
Dieser Fall liegt ein wenig komplizierter: In Abhängigkeit einer Bedingung wird entweder algo1 (n) oder algo2 (n ) ausgeführt. Zunächst werden die
Komplexitäten der Methoden bestimmt: Theta(g1(n)) und Theta (g2(n)).
Ein einfacher Weg ist die Abschätzung nach oben: Führte man beide Methoden algo1 (n) und algo2 (n) unabhängig von einer Bedingung hintereinander aus, kostet es auf jeden Fall mindestens so viel Rechenzeit, als wenn man durch if einen Fall ausspart.
Dann gilt wieder die Summenregel und der Gesamtaufwand liegt in Theta (max(g1 (n), g2(n))).
Also würde laut deiner Idee die Funktion in O(n^n), Omega(n) und Theta(n^n) liegen.
MfG und ein guten Start in die Woche
|
|
02.05.2011 09:20 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Naja, nicht ganz. Omega ist bei mir konstant und nicht linear...
Ich lass mal die Katze aus dem Sack:
So wäre groß und
VG und dir auch nen guten Start in die Woche,
Karlito
|
|
02.05.2011 09:46 |
|
|
Tai
Grünschnabel
Dabei seit: 27.04.2011
Beiträge: 5
|
|
Hallo,
danke für deine Hilfe. Was ich aber trotzdem noch nicht verstehe.
Deine Funktion ist in und in
aber die Funktion ist ja auch , und usw.
Genauso wie in
Aber
Somit ist ja auch
Analog dazu das Omega.
Dann wäre laut der Frage die Funktion nicht richtig.
Laut meinen Verständniss kann es sowas eigentlich garnicht geben
,
weil ist und .
Und dann wird immer oder liegen.
Viel dank für die Einsicht
|
|
02.05.2011 15:40 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Vlt hab ich da auch was falsch verstanden. Hatte O immer als obere schranke angesehen und Omega als untere...
Wenn du ne Lösung bekommst sag bescheid...
VG,
Karlito
|
|
03.05.2011 17:51 |
|
|
|