Lineær søgning
Fra Wikipedia, den frie encyklopædi
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.
