Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Komplexität > Eine Funktion N -> N soll weder in O(n) noch in Omega(n) liegen

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexität > Eine Funktion N -> N soll weder in O(n) noch in Omega(n) liegen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Komplexität > Eine Funktion N -> N soll weder in O(n) noch in Omega(n) liegen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

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

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie Tai in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Vorschlag: Was Alternierendes?

VG,

Karlito

27.04.2011 22:45

Nehmen Sie Karlito in Ihre Freundesliste auf

Tai
Grünschnabel

Dabei seit: 27.04.2011
Beiträge: 5

Also ich kenne Alternierendes nur aus der Mathematik und das wäre ja z.B.
f(x) : (-1)^x

Wäre das dann so etwas wie

code:
1: 2: 3: 4: 5: 6:	wenn i % 2 == 0 rückgabe 1 sonst rückgabe -1

oder

code:
1: 2: 3:	rückgabe -1^x

Aber das liegt ja in Groß-O(1)

Ich finde dabei keinen Lösungsansatz

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Tai: 28.04.2011 00:50.

28.04.2011 00:47

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hi,

nach der Aufgabenstellung, die du hier gestellt hast, reicht eine mathematische Formel welche eine Abbildung der Form $[latex]f\colon\, N\to N,\[/latex]$ ist. Also eine stinknormale Folge. Wie ein konkreter Algorithmus aussieht sollte unerheblich sein (das ist ja nur pure Theorie...).

Außerdem gibt es m.E. keine negativen komplexitäten, also ist -1 ein ungültiger Wert. Die Komplexitäten sind auch keine Ausgaben...

Besser wäre der Ansatz:

code:
1: 2: 3: 4: 5: 6:	wenn i % 2 == 0 wähle Algorithmus A sonst wähle Algorithmus B

Wobei die Algorithmen unterschiedliche Komplexitäten aufweisen.

[latex](-1)^n[/latex]

ist ein guter Ansatz. Jetzt musst du diesen Ansatz nur so umnwandeln, dass nicht nur [latex]1[/latex]

und

herauskommt sondern möglichst gleich 2 verschiedene Funktionen für gerade und ungerade [latex]n[/latex]

.

Tipp: Brüche

VG,

Karlito

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 28.04.2011 08:33.

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 Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Es soll darauf hinauslaufen (zumindest laut meiner Idee), dass die Folge für gerade [latex]n[/latex]

exponentiell wird und für ungerade [latex]n[/latex]

konstant. Nix mit 0/0 Augenzwinkern

2 Verschiedene Funktionen war ein wenig irreführend. Ich meinte, dass die Folge für je gerade und ungerade [latex]n[/latex]

verschiedene Verläufe hat.

VG,

Karlito

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 02.05.2011 07:30.

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 Karlito ist männlich

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:

$[latex]2^n*2^{(-1)^n*n}[/latex]$

So wäre groß [latex]O = 2^n[/latex]

und $[latex]\Omega = 1[/latex]$

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 verwirrt

,
weil

ist und

.
Und dann wird immer

oder

liegen.

Viel dank für die Einsicht Gott

02.05.2011 15:40

Karlito Karlito ist männlich

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

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexität > Eine Funktion N -> N soll weder in O(n) noch in Omega(n) liegen