Springsøgning
Springsøgning er sådan, du leder efter en side i en bog uden indholdsfortegnelse: du bladrer et stykke frem ad gangen og kigger på sidetallene, og når du er nået for langt, bladrer du tilbage gennem det sidste stykke. På en sorteret liste kræver den langt færre sammenligninger end at tjekke hver værdi.
Idéen
I en sorteret liste fortæller den sidste værdi i en blok, om målet overhovedet kan være i blokken: er den mindre end målet, er alle værdier i blokken også mindre. Så der er ingen grund til at kigge indenfor. Tjek den sidste værdi i hver blok efter tur, og spring hele blokke over, indtil en ikke er mindre end målet. Så kan målet kun være i den blok: gennemgå den fra starten.
Et eksempel
Søg efter 23 i 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 med blokke på 3. Den første blok slutter med 8, som er mindre, så spring den over. Den anden blok slutter med 23, som ikke er mindre, så 23 kan kun være i 12, 16, 23. Gennemgangen giver 12, 16 og så 23: fundet efter 5 sammenligninger, hvor lineær søgning kræver 6 og binær søgning 3. Søger man efter 40, fører blokenderne 8, 23 og 72 til blokken 38, 56, 72; 38 er mindre og 56 allerede større, så 40 er der ikke: igen 5 sammenligninger.
Hvorfor √n
Med blokke på m værdier kræver det højst omkring n/m sammenligninger at finde den rigtige blok og højst m at gennemgå den. Få, lange spring gør gennemgangen lang; mange korte spring gør springene mange. Summen n/m + m er mindst, når begge dele er lige store, ved m = √n, hvor den er omkring 2√n. For 40 værdier betyder det blokke på 6 og højst 13 sammenligninger; for en million værdier blokke på 1.000 og omkring 2.000 sammenligninger.
Hvor den passer ind
Binær søgning kræver færre sammenligninger, omkring log₂ n. Men binær søgning hopper frem og tilbage over hele listen, mens springsøgning kun går fremad og går tilbage én gang, til starten af én blok. Det gjorde den attraktiv for data på bånd eller i en kædet struktur, hvor det er langsomt at gå tilbage. Ben Shneiderman beskrev den som jump searching i 1978. Samme idé om at dele op i √n blokke, ofte kaldet kvadratrodsopdeling, findes i mange andre algoritmer.
Udforsk den
Åbn appen, vælg en værdi i Søg efter, og tryk på Trin. Hvert spring fremhæver den sidste værdi i en blok; oversprungne blokke falmer, og blokken, der kan indeholde målet, er skraveret, mens den gennemgås. Skift Springlængde fra √n til 2 eller 8 med 40 søjler, og se balancen mellem spring og gennemgang flytte sig.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten af springsøgning?
O(√n) med blokke på √n værdier: højst omkring 2√n sammenligninger. Den kræver O(1) ekstra hukommelse og en sorteret liste.
Hvad er forskellen på springsøgning og binær søgning?
Binær søgning halverer den resterende del hver gang og kræver omkring log₂ n sammenligninger, men går frem og tilbage. Springsøgning springer frem i faste skridt og gennemgår én blok, kræver omkring 2√n sammenligninger og går kun tilbage én gang.
Kan gennemgangen af den sidste blok bruge binær søgning i stedet?
Ja. Med binær søgning i blokken falder gennemgangen fra m sammenligninger til omkring log₂ m. Springene koster stadig n/m, så større blokke betaler sig da.
Kræver springsøgning en sorteret liste?
Ja. Det er kun sikkert at springe en blok over, fordi en mindre sidste værdi betyder, at alle værdier i blokken er mindre. Appen sorterer en usorteret liste først.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv springsøgning