Heim > System-Tutorial > LINUX > Algorithmus – Suche überspringen

Algorithmus – Suche überspringen

WBOY
Freigeben: 2024-02-16 10:42:02
nach vorne
635 Leute haben es durchsucht

Algorithmus – Suche überspringen

Angenommen, wir haben ein Array arr[] der Größe n und einen Block (zu springen) der Größe m. Dann durchsuchen wir die Indizes arr[0], arr[m], arr[2m]... ..arr[km] und so weiter. Sobald wir das Intervall gefunden haben (arr [km]

Wir betrachten das folgende Array: (0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610). Die Länge des Arrays beträgt 16. Bei einer Sprungsuche werden in den folgenden Schritten 55 gefunden, vorausgesetzt, die zu überspringende Blockgröße beträgt 4,

Schritt 1: Springe von Index 0 zu Index 4;
Schritt 2: Springen Sie von Index 4 zu Index 8;
Schritt 3: Springen Sie von Index 8 zu Index 16;
Schritt 4: Da das Element bei Index 16 größer als 55 ist, gehen wir einen Schritt zurück zu Index 9.
Schritt 5: Führen Sie eine lineare Suche ab Index 9 durch, um Element 55 zu erhalten.
Was ist die optimale Stückgröße zum Überspringen?
Im schlimmsten Fall müssen wir n/m Sprünge und m-1 Vergleiche mit einer linearen Suche durchführen, wenn der zuletzt überprüfte Wert größer als das gesuchte Element ist. Daher beträgt die Gesamtzahl der Vergleiche im ungünstigsten Fall ((n/m) + m-1). Wenn m =√n, ist der Wert der Funktion ((n/m) + m-1) der Minimalwert. Daher ist die beste Schrittgröße m = √n.

// C++ program to implement Jump Search

#include <bits>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>Ausgabe: </p>
<p>Nummer 55 ist bei Index 10</p>
<p>Zeitkomplexität: O(√n)<br>
Hilfsraum: O(1)</p>
<p><strong>Achtung:</strong></p>
<p>Diese Suche funktioniert nur bei sortierten Arrays. <br>
Die optimale Größe der zu überspringenden Blöcke ist O(√n). Dies macht die Sprungsuche O(√n) zeitlich komplex. <br>
Die zeitliche Komplexität der Sprungsuche liegt zwischen der linearen Suche ((O(n))) und der binären Suche (O(Log n) <br>).
Die binäre Suche ist besser als die Sprungsuche, aber die Sprungsuche hat den Vorteil, dass wir sie nur einmal durchlaufen (die binäre Suche erfordert möglicherweise höchstens 0 (Log n) Sprünge, wenn man bedenkt, dass das gesuchte Element das kleinste Element oder kleiner als das kleinste ist). Daher verwenden wir in Systemen, in denen das Zurückspringen teuer ist, die Sprungsuche. </p></bits>
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonAlgorithmus – Suche überspringen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:linuxprobe.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage