Das Wortproblem Typ 1 für kontextsensitive Sprachen ist entscheidbar.

Bzgl. der Komplexität ist es NP-schwierig.

O(k^n) Komplexität

Laut der Folie kann man nicht zeigen, dass es in NP liegt. Es ist NP-schwierig.

Nun meine Frage: Ist das Wortproblem Typ 1 Turing-Maschinen berechenbar? Ja oder Nein, wenn es wie hier angegeben NP-schwierig ist?
Es gilt P Teilmenge von NP.

Wie löst man die obige Aufgabe. Habe mir jetzt ein paar Videos zum Thema angeschaut und kann ein paar Algorithmen analysieren. Bei obigem komme ich aber nicht weiter.

Beim ersten Algorithmus muss ich die Multiplikation ja jedes mal durchführen, während beim zweiten nur ein einziges mal am Ende multipliziert wird. Daher hätte ich gesagt:

1. Algorithmus O(n), da ich die Multiplikation jedes mal durchführen muss
2. Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Meine Fragen:

1. Ist die Analyse korrekt?
2. Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?
3. Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

Hallo,

wenn ich einen Code wie folgenden hab, zähle ich dann einfach die Anzahl der Operationen und setze sie ins Verhältnis mit der Elementanzahl? Ist das berechnen einer Variable wie "middle" gleichwertig mit einem Vergleich (O(1))? Im Falle des ersten, großen Feldes wird der Algorithmus bis zum Ergebnis insg. 6 mal aufgerufen und hat je 2 Vergleiche und ein mal middle berechnen. D.h bei 20 Elementen 18 (mit Variable berechnen) bzw 12 (nur die Vergleiche) Operationen. Aber wie man ab da weitermacht, weiss ich nicht. Wäre die Komplexitätsklasse in dem Fall dann (O(n))?

Danke für eure Hilfe

Hallo, ich hab die O-Notation schon so mehr oder weniger verstanden, also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.

Was ich aber nicht verstehe, wie man das bei mathematischen Ausdrücken zeigen soll. Z.B.:

Was ich mir vorstellen könnte wäre, dass n die Eingabe entspricht und der Funktionswert der dann rauskommt gleich der Eingabe hoch vier entsprechen muss (ist hier ja aber nicht der Fall).

Ich habe die Aufgabe folgendermaßen gelöst :

Ist das richtig ? Ich habe den Eindruck, es fehlt etwas.

Vielen Dank!

Ich verstehe nicht, was der Unterschied zwischen der O-Notation und der asymptotischen Laufzeit ist. Beide beschreiben die Abhängigkeit der Laufzeit zur Problemgrösse und lassen uns die Algorithmen in verschieden Klassen einteilen, aber was ist der Unterschied?

Aufgabe: O-Notation

Ist die folgende Aussage korrekt?

Wie beweise oder widerlege ich diese Aussage? Besten dank im voraus. :)

Hallo zusammen,

ich habe eine Verständnisfrage zur Aufgabe a und c (siehe Anhang).

Es ist ja so, dass bei a, im Grunde doch beides gleich schnell wächst, so dass wenn ich beispielsweise als konstante 999 wähle, dass 999 * n^7 / 2n^7 + 1000n^7 zu einer endlichen Zahl führt..

Laut der Definition, darf die Funktion nur höchstens so schnell wachsen wie n hoch 7, und da beide gleich schnell wachsen, trifft dies doch zu, oder?

Bei C habe ich nun aber das gleiche Ergebnis, hier ist es ja so, dass die Funktionnur gleich schnell wachsen darf, wie n quadrat, und auch hier trifft dies zu, da wenn ich beide dividiere, immer ein endliches Ergebnis dabei herauskommt, richtig?

Dementsprechend ist es doch so, dass beispielsweise die Aufgabe a, sowohl stimmen würde, wenn dort das O als auch das Theta (O mit einem Strich in der Mitte) stehen würde, oder?

Freue mich riesig über eine Erklärung!

Weiterhin muss ich solche Aufgaben wie im Anhang zu sehen, beweisen. Wie gehe ich da vor? Muss ich da einfach die Funktion durch g(n) teilen, und bestimmen, ob ein endlicher Wert rauskommt etc, oder es zu 0 führt, bei n gegen unendlich, und dementsprechend einordnen?

LG

Hallo zusammen,

ich verstehe die O-Notation nicht genau, und wollte daher zu gegebenen Beispielen fragen, ob ich dies so richtig verstanden habe. Falls nicht, würde ich mich riesig über eine Erklärung freuen.

(Siehe Anhang)

Bei der ersten Aufgabe, ist es doch so, dass die Funktion höchstens so schnell wachsen darf, wie n hoch 7.

Wenn ich hier beispielsweise allerdings jegliche Zahl einsetze, so wächst es doch einwenig schneller als n hoch 7? So, dass dies nicht stimmen dürfte, oder?

Bei der zweiten Aufgabe darf die Funktion nur mindestens so schnell wachsen wie n hoch 7. Hier würde die Aussage doch zutreffen, da dies immer ein wenig höher ist, wenn man eine beliebe Zahl einsetzt, im Gegensatz zu n hoch 7, oder?

Bei der dritten Aufgabe darf die Funktion nur genau so schnell wachsen wie n quadrat.

Dies trifft allerdings nicht zu, oder?

Freue mich über jede Erklärung!

LG

Hallo,

im Fach "Algorithmen und Datenstrukturen" muss ich die O-Notation beweisen.

Ich habe viel nachgelesen und verstehe trotzdem nicht wie ich das beweisen kann.

Ich habe absolut keine Ahnung wie ich vorgehen muss. :/

Die Aufgabe:

Bestimmen Sie, obf∈O(g) oderf∈Ω(g) oder beides (d.h.f∈Θ(g)). Beweisen Sie IhreAussagen unter Verwendung der Definitionen aus der Vorlesung.

f(n) g(n)

a) n^3/2 n^2/3

b) 10n^2+ log^2(n) n^2

c) 2^n 2^n+^4 + 3

d) 2^n 10n!

Ich würde mich sehr freuen, wenn mir jemand bei dieser Aufgabe helfen kann und

es mir für "dummies" erklären kann.

Danke schonmal im Vorraus!

Hallo, ich habe leider etwas Probleme diese Form der Stirlingformel (siehe unten)in Verbindung mit der O-Notation zu verstehen. Leider ist mir unklar wie ich das Theta 1/n verstehen muss, da ich es immer als eine Art Menge von Funktionen aufgefasst habe und das für mich in diesem Kontext nicht wirklich Sinn ergibt. Kennt sich jemand damit aus und kann es mir erklären?

Über eine Antwort würde ich mich sehr freuen.

MfG



ja hey :)

ist diese Aussage korrekt?

2²ⁿ €O(2ⁿ)

Dankeschön :)