Lineær søgning

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.

Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.