Wyszukiwanie liniowe

Lekcja 9 z 26 w kursie Tablice w C++ w Coddy.

Aby znaleźć szukany element w tablicy, używamy prostej metody nazywanej wyszukiwaniem liniowym.

Jak sugeruje nazwa, działa ono w czasie liniowym, czyli potrzeba O(n) czasu na wyszukanie elementu, ponieważ musimy przejść przez całą tablicę, aby znaleźć szukaną liczbę.

Załóżmy, że k jest elementem, który musimy znaleźć, a dana jest tablica. Musimy przejść przez całą tablicę i jeśli znajdziemy element, musimy wypisać YES, w przeciwnym razie wypisujemy NO.

for(int i=0;i<n;i++){
   if(arr[i]==k){
     cout<<"YES"<<endl;
   }else{
     cout<<"NO"<<endl;
   }
}

Analiza złożoności czasowej

Najlepszy przypadek to taki, w którym szukany element znajduje się na pierwszym indeksie — w takim przypadku wyszukiwanie zajmie stały czas. Najgorszy przypadek to taki, w którym element znajduje się na ostatnim indeksie; wtedy złożoność czasowa wynosi n. Dlatego złożoność czasowa wyszukiwania liniowego wynosi O(n), gdzie n to liczba elementów w tablicy.

Wyzwanie

Mając tablicę, znajdź sumę wszystkich jej elementów.

Spróbuj swoich sił

#include<iostream>
using namespace std;

int main(){

 
  int n;
  cin>>n;

  int arr[n];
  
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  

 //Write your code here 





    return 0;
}