Lineare Suchzeit Komplexität

Lineare Suche ist eine sequentielle Suche. Diese Methode zum Suchen überprüft die Elemente der Liste von eins von eins, beginnend vom ersten Element. Wenn es das erste Ereignis des Elements sieht, nach dem es sucht, stoppt die Suche. Das Element, das es sucht, wird als Ziel bezeichnet. Wenn das Element nicht gefunden wird, werden alle Elemente in der Liste überprüft. Die lineare Suche ist ein sehr einfacher Suchalgorithmus, den jeder Programmierer offiziell oder intuitiv lernen sollte.

Betrachten Sie die folgende Liste:

I j a c b g d h e f

Um nach A zu suchen, muss das Programm die Liste dreimal iterieren. Um nach G zu suchen, muss das Programm die Liste 6 Mal iterieren. Um nach F zu suchen, muss das Programm die Liste 10 Mal iterieren. Um nach K oder einem Brief zu suchen, der nicht in der Liste steht, muss das Programm die Liste 10 Mal iterieren und findet keine Übereinstimmung.

Ziel dieses Artikels ist es, die zeitliche Komplexität für die lineare Suche zu erstellen. Die Programmierung erfolgt in der folgenden C -Diskussion.

Linearer Suchalgorithmus

Der Algorithmus für die lineare Suche ist einfach. Angenommen, die Liste ist ein auf Null-Indexed basierendes Array. Lassen Sie die Variable, die jeden Index darstellt. Lassen Sie das Array den Namen a haben. Die Schritte sind wie folgt:

• • Lass ich 0 sein.
  • Wenn ein [i] das Ziel ist, wird der Wert für I zurückgegeben und die Suche erfolgreich endet.
  • Wenn ein [i] nicht das Ziel ist, erhöhen Sie I um 1 und wiederholen Sie den vorherigen Schritt.
  • Während ich weniger als N ist, wobei n die Länge des Arrays ist, wiederholen Sie die beiden vorherigen Schritte in der Reihenfolge.
  • Fahren Sie auf diese Weise fort, bis das Ziel entweder gefunden oder nicht gefunden wurde.

Die Suche endet erfolgreich, wenn das Ziel gefunden wird. Die Suche endet erfolglos, wenn das Ziel nicht gefunden wird. Für ein erfolgloses Ende werden alle N -Elemente überprüft.

Zeitkomplexität

Zeitkomplexität ist die Anzahl der Hauptvorgänge für einen Code, um seine Aufgabe zu erledigen. Überprüfen Sie, ob das Ziel mit einem Element übereinstimmt. Es gibt die Zeitkomplexität der schlechteren Fall, die Komplexität der durchschnittlichen Fallzeit und die Best-Case-Zeitkomplexität.

Schlechtere Zeitkomplexität

Die maximale Anzahl von Operationen tritt auf, wenn sich das Ziel am Ende der Liste befindet oder überhaupt nicht in der Liste steht. Dies ist der schlechtere Fall. Die Komplexität des schlechteren Falles wird als:

An)

Dies verwendet die Big-O-Notation. Die Big-O-Notation beginnt mit dem Großbuchstaben O, gefolgt von Klammern. Innerhalb der Klammern ist der Ausdruck für die Anzahl der Operationen zur Lösung der Aufgabe.

Best-Case-Zeit-Komplexität

Wenn das erste Element der Liste das Ziel ist, ist für die Suche nur ein Überprüfungsvorgang erforderlich. Das heißt, für die Suche ist nur eine Operation erforderlich. Dies ist die Best-Case-Zeitkomplexität. Es ist geschrieben als:

O (1)

Wobei 1 in den Klammern eine Operation bedeutet.

Durchschnittsfallzeitkomplexität

Die durchschnittliche Fallzeitkomplexität hängt von der Wahrscheinlichkeitsverteilung ab. Wenn jedes Element in einer Position sein kann, ist es gleich wahrscheinlich, dass jedes Element durchsucht wird. In dieser Situation wird die Komplexität der durchschnittlichen Fallzeit als:

O (n/2)

Programmierung in c

Die lineare Suche ist wahrscheinlich die einfachste Suche, um ein Programm zu schreiben. Folgen Sie einfach dem Algorithmus, der hier wiederholt wird, um eine einfache Referenz zu erhalten:

• • Lass ich 0 sein.
  • Wenn ein [i] das Ziel ist, wird der Wert für I zurückgegeben und die Suche erfolgreich endet.
  • Wenn ein [i] nicht das Ziel ist, erhöhen Sie I um 1 und wiederholen Sie den vorherigen Schritt.
  • Während ich weniger als N ist, wobei n die Länge des Arrays ist, wiederholen Sie die beiden vorherigen Schritte in der Reihenfolge.
  • Fahren Sie auf diese Weise fort, bis das Ziel entweder gefunden oder nicht gefunden wurde.

Im Wesentlichen lautet das Programm wie folgt:

#enthalten
int linearsearch (char a [], int n, char t)
für (int i = 0; iif (t == a [i])
kehre I zurück;

Es beginnt mit der Einbeziehung des Stdio.H Bibliothek, die für Eingabe und Ausgabe verantwortlich ist. Danach gibt es die Funktionslinearsearch () -Funktionsdefinition. Der Hauptcode in der Funktionsdefinition ist der For-Loop. Der For-Loop scannt das Array vom Anfang bis zum Ende und sucht nach einer Übereinstimmung mit dem Ziel. Wenn ein Ziel gefunden wird, wird der Index für das Matching -Element im Array zurückgegeben. Um die Ordnungsnummer des Index des übereinstimmten Elements zu erhalten, fügen Sie 1 zum Null-basierten Index hinzu.

Eine geeignete C -Hauptfunktion für das obige Programm lautet wie folgt:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'i', 'j', 'a', 'c', 'b', 'g', 'd', 'H', 'e', ​​'f';
int ret = lineararsearch (a, n, 'g');
printf ("%i \ n", ret);
Rückkehr 0;

Die erste Aussage der C -Hauptfunktion deklariert die Anzahl der Elemente im angegebenen Array. Danach gibt es das Array mit dem Namen a. Es gibt zehn Zeichen im Array. Die Erklärung des Arrays beginnt mit "Char" und nicht mit "int". Von dort aus wird die definierte Funktion linearearsearch () aufgerufen. Das erste Argument für den Funktionsaufruf ist das Array. Das zweite Argument ist die Anzahl der Elemente im Array. Das dritte Argument ist das Ziel, das der Brief ist, dessen Anwesenheit im Array überprüft wird. Wenn es vorhanden ist, wird der Null-basierte Index zurückgegeben. Wenn es nicht vorhanden ist, wird nichts zurückgegeben.

Die nächste Anweisung druckt einen zurückgegebenen Index aus. Für diese C -Hauptfunktion wird 5 ausgedruckt. Wenn 1 zu 5 hinzugefügt wird, wäre es 6, was der Ordinalindex ist.

Abschluss

Die Komplexität des schlechteren Falles wird als:

An)

Dies verwendet die Big-O-Notation. Die Big-O-Notation beginnt mit dem Großbuchstaben O, gefolgt von Klammern. Innerhalb der Klammern ist der Ausdruck für die Anzahl der Operationen zur Lösung der Aufgabe.

Wenn das erste Element der Liste das Ziel ist, ist für die Suche nur ein Überprüfungsvorgang erforderlich. Das heißt, für die Suche ist nur eine Operation erforderlich. Dies ist die Best-Case-Zeitkomplexität. Es ist geschrieben als:

O (1)

Wobei 1 in den Klammern eine Operation bedeutet.

Die Komplexität der Durchschnittsfallzeit hängt von der Wahrscheinlichkeitsverteilung ab. Wenn sich jedes Element in einer Position befinden kann, ist jedes Element mit diesem Algorithmus ebenso wahrscheinlich durchsucht. In dieser Situation beträgt die Komplexität der Durchschnittsfallzeit:

O (n/2)