Lineær søgning

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

Lineær søgning er det samme som sekventiel søgning og beskriver princippet at gennemsøge et løsningsrum fra ende til anden indtil løsningen er fundet. Hvis der findes en løsning, vil lineær søgning altid finde den.

Tidskompleksitetet for lineær søgning er O(N), hvor N er antallet af mulige løsninger. Hvis data er tilfældigt distribueret, vil lineær søgning gennemsnitligt finde denne efter N/2 sammenligninger. I bedste tilfælde er løsningen det første element, der undersøges, og kun en enkelt sammenligning behøves. I værste fald er løsningen slet ikke at finde i løsningsrummet og der behøves N sammenligninger.

Programmering Stub
Denne artikel om datalogi eller et datalogi-relateret emne er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.