Landausymbole, Theta, Laufzeit < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Es geht um die lineare Suche. Dabei hat der Algorithmus eine lineare Laufzeit nur abhängig von n, der Eingabegröße. Sei diese f(n).
Ein Array hat Elemente, ein Algorithmus sucht in diesem Array nach einem bestimmten Element.
Angenommen im Mittel befindet sich das gesuchte Element gleichwarscheinlich an einer beliebigen Stelle im Array.
Damit wäre es doch im Schnitt, in der Mitte des Arrays, bei n/2, oder?!
Wie verhält sich die Laufzeit im mittleren Fall, bzw. im schlimmsten Fall?
Und DA kommt mein Problem, ich bin mit den Landausymbolen nicht sooo per Du... :)
Meine Idee:
Im mittleren Fall ist das Element in der Mitte, also bei n/2. Dann wäre die Laufzeit f(n) = n/2
Im schlimmsten Fall ist es das letzte Element, dann wäre die Laufzeit f(n) = n
Ausgedrückt in Landausymbolblabla:
n [mm] \wedge [/mm] n/2 [mm] \in \Theta(g(n)) [/mm] | g(n) = n
Ist das so richtig?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:09 Mo 19.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
