Informatiker Board | Theoretische Informatik | Landau, Groß O und Theta usw.

Informatiker Board » Themengebiete » Theoretische Informatik » Landau, Groß O und Theta usw.

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Landau, Groß O und Theta usw.

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

Landau, Groß O und Theta usw.

Zitatantwort auf diesen Beitrag erstellen

Ich hoffe ihr verzeiht, wenn ich hier ein paar etwas banale Fragen stelle.

Es geht um Laufzeiten von Algorithmen.

Es geht um die lineare Suche (finde in einem array ein element, wenn da liefere index, sonst NIL), diese hat ja eine lineare Laufzeit, abhängig von n.

(Falls ich an irgendeiner Stelle Dummfug rede, bitte ich um kreative Kritik großes Grinsen

)

Ich sag also jetzt mal einfach so: Laufzeit der Suche sei f(n)

(ist das bis dahin richtig?)

Jetzt gehts darum: Angenommen, das gesuchte Element befindet sich statistisch gesehen im Mittel, in der Mitte des Arrays. Damit hätte man eine mittlere Laufzeit von n/2 (wenn n die größe des Arrays ist) und im schlimmsten Fall eine Laufzeit von n.

Ausgedrückt in LaundauSymbolen in diesem fall Theta:

Die beiden Laufzeiten (mittlerer und schlimmster Fall) ausgedrückt in Theta wäre doch:

Theta(von schlimmster Fall) und Theta(von mittlerer Fall) sind element von h(n) = n

(kann mir jemand so folgen?)

__________________
I'm 71% Megatron!

17.11.2007 10:58

Nehmen Sie JROppenheimer in Ihre Freundesliste auf

MSN Passport-Profil von JROppenheimer anzeigen

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Du hast f(n) eingeführt aber nicht h(n).

Zitat:

Theta(von schlimmster Fall) und Theta(von mittlerer Fall) sind element von h(n) = n

Diese Aussage solltest du in dieser Form nochmal überdenken.

Was ist $[latex]\Theta(n)[/latex]$ mathematisch gesehen für ein Konstrukt? Wie ist es definiert?

17.11.2007 11:07

Nehmen Sie Tobias in Ihre Freundesliste auf

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

1. wie mache ich formeln großes Grinsen

2. theta von n ist eine menge von funktionen, die "im wesentlichen" wie n wachsen (in diesem fall linear?)

ich kenne die mathematische definition, mit c0 und c1 und n aus N und so

edit: geil, danke für die schnelle antwort, ich weiss das zu schätzen!!!

edit²: Sorry, das sollte so heissen:

Laufzeit(von schlimmster Fall) und Laufzeit(von mittlerer Fall) sind element von Theta von(h(n) = n)

__________________
I'm 71% Megatron!

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von JROppenheimer: 17.11.2007 11:36.

17.11.2007 11:25

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Zitat:

Laufzeit(von schlimmster Fall) und Laufzeit(von mittlerer Fall) sind element von Theta von(h(n) = n)

Genau, so wird ein Schuh draus. Theta ist eine Menge, in der Abbildungen die Elemente sind.

Formeln gehen mit latex zwischen

code:
1:	[latex] .. [/latex]

Klammern.

17.11.2007 12:45

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

Ich muss sagen, dass mir trotzdem das Verständnis ein bisschen schwer fällt:

Das heisst, dass lineare Laufzeiten im Grunde alle "gleich" im Sinne von Theta sind?! Also jede lineare Laufzeit ist element von Theta(h(n) = n) ??

Vielen Dank für die Hilfe!!!

__________________
I'm 71% Megatron!

17.11.2007 13:48

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Du kannst dir die Landaunotation als "Gruppierung" von Laufzeiten vorstellen. In der Komplexitättheorie interessiert es oft nicht, ob eine Funktion eine Laufzeit von $[latex]\frac{n}{2} + 300[/latex]$ oder [latex]2n + 2[/latex]

hat. Wichtig ist die asymptotische Laufzeit, d.h. welcher Teil der Laufzeit dominiert. $[latex]\Theta(n)[/latex]$ beschreibt die Klasse der Funktionen, die (asymptotisch) linear wachsen. Die wichtige Information hieraus ist, wie sich die Laufzeit verändert, wenn die Eingabegrößen anwachsen.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 17.11.2007 15:13.

17.11.2007 15:11

JROppenheimer
Foren As

Dabei seit: 17.11.2007
Beiträge: 94

Gut, soweit kann ich folgen. Aber ist dann Theta im Grunde nicht das einzige, was man braucht? Wozu brauche ich denn dann noch groß O und groß Omega?
Kann ich am Ende nicht jede Laufzeit auf eine Thetadarstellung führen? Die ist doch am aussagekräftigsten, oder?

__________________
I'm 71% Megatron!

17.11.2007 16:44

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

$[latex]\Theta[/latex]$ gibt eine schärfere Schranke an als z.B. $[latex]\mathcal{O}[/latex]$ .

z.B.:
$[latex]\log(n) \in \mathcal{O}(n), \; \log(n) \notin \Theta(n)[/latex]$

17.11.2007 17:44

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Landau, Groß O und Theta usw.