Złożoność obliczeniowa w algorytmie szukania lidera- błędne myślenie?

pytanie zadane 10 sierpnia 2020 w C i C++ przez 83nt13m4n Nowicjusz (140 p.)

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 
      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.

2 odpowiedzi

odpowiedź 10 sierpnia 2020 przez Wiciorny Ekspert (269,590 p.)
edycja 10 sierpnia 2020 przez Wiciorny

 "if( T[i] == lider)"

No okej, ale "wartość i " jest zależna od czego ?
No jest zależna tylko i wyłącznie od N, przypadek złożoności oceniamy jako NAJBARDZIEJ PESYMISTYCZNE ROZWIĄZANIE. A ono jest zależne od N. Ilość porównań dla "zmiennej i" jest zawsze lub lepiej tłumacząc NIGDY NIE będzie większa niż n, bo taki mamy warunek.... a, że i-tą iteracje zaczynamy od wartości 1, to w najgorszym przypadku funkcja wykona się N-1 razy ... bo fakt że jeśli wejdzie w 1 warunek, to else if też się wykona. ale to jest traktowane jako 1 operacja- 1 funkcja ograniczona N RAZY

Zauważ że zawsze wykona się jedno porównanie, jeśli 1- będzie prawdziwe to nie wykona się pozostałe, jeśli nie bedzię prawdziwe to wykona się jedno z pozostałych

komentarz 11 sierpnia 2020 przez jankustosz1 Nałogowiec (35,880 p.)

Zauważ że zawsze wykona się jedno porównanie, jeśli 1- będzie prawdziwe to nie wykona się pozostałe, jeśli nie bedzię prawdziwe to wykona się jedno z pozostałych

To że porównanie zwraca fałsz nie znaczy, że się nie wykonało. Jeżeli pom > 0 i T[i] != lider to wykonają się 2 porównania. Nie mówię, że to źle, albo że to robi jakąś różnicę, tylko zwracam uwagę, że autor pytania ma rację.

komentarz 11 sierpnia 2020 przez Wiciorny Ekspert (269,590 p.)

nie ma racji, bo podstawą jest zrozumienie pojęcia SCOPE I TERAZ wiedząc czym jest zasięg złożoności, zrozumie autor, że nie liczymy operacji każdej z osobna, autor KSIĄŻKI określa złożoność obliczeniową, a nie zlicza ilosć operacji na funkcje

komentarz 11 sierpnia 2020 przez jankustosz1 Nałogowiec (35,880 p.)

Autor podaje, że w tej części algorytmu porównań będzie n-1.

Twierdzisz, że autor ma rację?

komentarz 11 sierpnia 2020 przez Wiciorny Ekspert (269,590 p.)

tak twierdze, że AUTOR KSIĄŻKI ma racje i złożoność obliczeniowa jest tutaj liniowa
O(n) - tutaj szczególnie O(n-1) :) i nawet indukcyjnie możesz to wyprowadzić ze wzoru ...

komentarz 11 sierpnia 2020 przez tkz Nałogowiec (42,000 p.)

SCOPE I TERAZ wiedząc czym jest zasięg złożoności, zrozumie autor, że nie liczymy operacji każdej z osobna, autor KSIĄŻKI określa złożoność obliczeniową, a nie zlicza ilosć operacji na funkcje

To czym według Ciebie jest złożoność obliczeniowa jak nie ilością operacji jakie trzeba wykonać w postaci funkcji? Złożoność określa się dla całej funkcji, nie jej wycinka. Nawet jeżeli mamy jedna część o złożoności O(log n), która znajduję się pętli, to złożoność końcowa będzie O(n log n). Algorytm ma taką złożoność, jak jego najbardziej czasochłonny fragment.

Nieścisłości mogą wynikać z tłumaczenia źródła z jakiego korzysta autor.

komentarz 11 sierpnia 2020 przez jankustosz1 Nałogowiec (35,880 p.)

@Wiciorny, To że złożoność obliczeniowa jest liniowa nie mam żadnych wątpliwości. Ale autor książki/tłumacz napisał, że porównań będzie n-1

komentarz 11 sierpnia 2020 przez Wiciorny Ekspert (269,590 p.)

Złożoność czasowa algorytmu jest rozpatrywana jako ilość czasu potrzebnego do rozwiązania problemu w zależności od liczby danych wejściowych. Podawanie złożoności obliczeniowej w jednostkach czasu jest jednak nieprecyzyjne, bo wynik zależy również od szybkości działania komputera. Dlatego złożoność obliczeniowa algorytmu najczęściej podawana jest w liczbie wykonanych operacji i jest to największa liczba operacji dominujących wykonywanych w algorytmie dla dowolnego układu danych.

odpowiedź 10 sierpnia 2020 przez jankustosz1 Nałogowiec (35,880 p.)

Masz rację porównań będzie więcej niż n, autor był nieprecyzyjny.

Miał na myśli złożoność i ona jest zależna liniowo od n, tylko próbował to napisać prostymi słowami.