Złożoność obliczeniowa(Szukanie lidera), problem z interpretacją.

0

Dzień dobry,
mam mały problem z zliczeniem porównań w algorytmie znajdowania lidera w zbiorze. Mianowicie chodzi mi o tą część algorytmu:
...

for(int i =1; i<n; i++)
{
   if( pom == 0 )                                //PORÓWNANIE PIERWSZE WYKONA SIĘ n-1 razy
   {
      lider = T[i];
      pom = 1;
   }
   else if( T[i] == lider)                       //PORÓWNANIE DRUGIE WYKONA SIĘ TYLE RAZY ILE PIERWSZE BĘDZIE FAŁSZYWE
      pom++;
   else
      pom--;
}

...
Otóż autor pisze: "(...) W pierwszej pętli(to jest ta powyżej), w której szukamy kandydata na lidera, mamy n-1 wykonań pętli, co określa liczbę porównań.(...)". Autor podaje, że w tej części algorytmu porównań będzie n-1.
No i teraz według mnie porównań będzie tutaj więcej niż n-1. Samo to porównanie "if( pom == 0 ) " wykona się n-1 razy, a te porównanie "if( T[i] == lider)" tyle razy ile poprzednie będzie fałszywe. Czy mógłby ktoś mnie nakierować gdzie robię błąd w moim myśleniu? Pozdrawiam i z góry dzięki.

0

Jest n - 1 obiegów pętli, w niej instrukcja sterująca: if, else if, oraz else, każda z tych nich wykona się raz na obieg pętli.

1 użytkowników online, w tym zalogowanych: 0, gości: 1