Lider, idol i min-max za jednym przejściem

🎯 Po co Ci to?

Na deser działu — trzy perełki algorytmiczne, które łączy jedno hasło: nie sortuj, skoro nie musisz. Po sześciu jednostkach o porządku łatwo nabrać odruchu „posortuję i będzie widać" — a tymczasem wiele pytań o dane ma odpowiedzi tańsze o klasę: znaleźć najmniejszy i największy element, wskazać wartość okupującą większość listy, wyłowić „gwiazdę" spośród bywalców. Te algorytmy to klasyka polskiej matury rozszerzonej — i świetny trening patrzenia, ile informacji naprawdę potrzebuje odpowiedź.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• znaleźć minimum i maksimum jednocześnie, oszczędzając ćwierć porównań (metoda par);
• wyznaczyć lidera listy (element o większości wystąpień) w jednym przejściu;
• rozwiązać problem idola (celebryty) eliminacją kandydatów.

🔁 Przypomnij sobie

Z 1.2/3.4: maksimum jednym przejściem z kandydatem; z 6.5: klasa $O(n)$ bije $O(n \log n)$ — jeśli tylko zadanie na nią pozwala.

📘 Wyjaśnienie

Min i max naraz. Osobno: maksimum kosztuje $n-1$ porównań, minimum drugie tyle — razem $2n - 2$. Można taniej — parami: bierz elementy po dwa, porównaj je ze sobą (1 porównanie), większego z pary porównaj z dotychczasowym maksimum (1), mniejszego z minimum (1). Trzy porównania na dwa elementy zamiast czterech — łącznie około $\tfrac{3n}{2}$ zamiast $2n$:

def min_max(L):
    if len(L) % 2 == 1:
        mn = mx = L[0]; start = 1          # nieparzysta: pierwszy solo
    else:
        mn, mx = min(L[0], L[1]), max(L[0], L[1]); start = 2
    for i in range(start, len(L) - 1, 2):  # krok co 2: pary
        a, b = L[i], L[i + 1]
        if a > b:
            a, b = b, a                    # a to mniejszy z pary, b większy
        if a < mn: mn = a
        if b > mx: mx = b
    return mn, mx

Skąd zysk? Z podziału ról: przegrany wewnętrznego pojedynku nie ma szans na tytuł maksimum, więc nie zawracamy nim głowy mistrzowi — dokładnie ta logika, którą w 1.2 (zadanie 2) tłumaczyłeś, czemu algorytm „nie musi porównywać b z c". Ćwierć porównań to nie rewolucja klasy — ale metoda par to wzorzec myślenia „każde porównanie ma nieść maksimum informacji", i bywa pytaniem egzaminacyjnym wprost.

Lider: większość jednym przejściem. Lider listy to wartość występująca więcej niż $n/2$ razy (uwaga: może nie istnieć!). Podejście siłowe — zlicz każdą wartość — działa, ale wymaga pamięci na liczniki. Algorytm Boyera–Moore'a (1981) robi to jedną zmienną-kandydatem i licznikiem, obserwacją godną szachisty: skreśl parę różnych elementów — lider (jeśli był) pozostaje liderem reszty (usunąłeś mu co najwyżej jeden głos i dokładnie jeden głos przeciwny):

def lider(L):
    kandydat, licznik = None, 0
    for x in L:
        if licznik == 0:
            kandydat, licznik = x, 1       # nowy pretendent
        elif x == kandydat:
            licznik += 1                   # swój: głos za
        else:
            licznik -= 1                   # obcy: skreślamy parę
    # kandydat to JEDYNY możliwy lider — ale trzeba go zweryfikować!
    if L.count(kandydat) > len(L) // 2:
        return kandydat
    return None

Dwa przejścia (wyłonienie + weryfikacja), zero dodatkowej pamięci. Weryfikacja nie jest ozdobą: pierwsza faza obiecuje tylko tyle, że jeśli lider istnieje, to jest nim kandydat — dla listy [1, 2, 3] kandydatem skończy 3, a lidera nie ma wcale. Opuścisz drugie przejście — algorytm zacznie widywać liderów tam, gdzie ich nie ma (i to jest dokładnie błąd, na który poluje ta pozycja w arkuszach maturalnych).

Idol: gwiazda wśród bywalców. Scenka: na przyjęciu jest $n$ osób; idol to ktoś, kogo znają wszyscy, a on nie zna nikogo. Możesz zadawać pytania „czy osoba A zna osobę B?". Naiwnie: wypytaj każdego o każdego — $n^2$ pytań. Eliminacja robi to w $O(n)$: zapytaj A o B — jeśli A zna B, to A nie jest idolem (idol nie zna nikogo); jeśli nie zna, to B nie jest idolem (idola znają wszyscy). Każde pytanie skreśla jedną osobę! Po $n-1$ pytaniach zostaje jeden kandydat — którego (jak lidera!) trzeba zweryfikować dwoma seriami pytań (czy wszyscy go znają? czy on nie zna nikogo?). Razem ~$3n$ pytań zamiast $n^2$.

💭 Pomyśl: Co łączy wszystkie trzy algorytmy tej jednostki — parami, lidera i idola — na poziomie strategii? Sformułuj wspólną zasadę jednym zdaniem.

Sprawdź odpowiedź

Każde porównanie/pytanie nieodwołalnie eliminuje kogoś z gry (przegrany pary nie walczy o maksimum; skreślona para głosów nie zmienia lidera; każde „zna/nie zna" skreśla osobę) — dzięki czemu liczba operacji jest proporcjonalna do liczby uczestników, nie par. Zasada: projektuj pytania tak, by każda odpowiedź trwale zmniejszała pole gry. To ta sama dusza, co w połowieniu (1.4) — tyle że tam odpadała połowa, tu „tylko" jeden, ale za jednostkowy koszt. Algorytmika liniowa to sztuka niemarnowania odpowiedzi.

🧮 Prześledź

lider([5, 3, 5, 5, 2, 5, 3]) — tabelka: element, kandydat, licznik. Potem weryfikacja.

Sprawdź odpowiedź

5→(5,1); 3→(5,0); 5→ licznik 0, nowy pretendent (5,1); 5→(5,2); 2→(5,1); 5→(5,2); 3→(5,1). Kandydat 5; weryfikacja: count(5) = 4 > 7//2 = 3 ✓ — lider to 5. Zwróć uwagę na moment „licznik 0 i nowy pretendent tym samym elementem" — algorytmowi wolno „zapomnieć" wszystko, co widział: skreślone pary są naprawdę skreślone, historia nie wraca.

⚠️ Uwaga, pułapka

„Więcej niż $n/2$" to ostra większość — dla $n = 7$ trzeba co najmniej 4 wystąpień, nie 3,5 zaokrąglonego w dół. Warunek > len(L) // 2 jest poprawny (7//2 = 3, żądamy > 3, czyli ≥ 4 ✓), ale >= len(L) // 2 już kłamie na parzystych ($n=6$: trzy wystąpienia to dokładnie połowa — NIE większość). Jedna kreska w nierówności, klasyczna maturalna mina — testuj na $n$ parzystym z remisem pół na pół.

🛠️ Teraz Ty

Bez komputera: rozegraj idola dla czterech osób z macierzą znajomości, którą sam ułożysz (najpierw z idolem, potem bez — co wtedy pokaże weryfikacja?). Z komputerem: zaimplementuj wszystkie trzy; dla min_max policz porównania na liście $n = 1000$ i sprawdź obiecane ~1500; dla lider przetestuj brzeg „lidera brak" i listę jednoelementową.

📐 Definicje tej lekcji

• Metoda par (min-max) — pojedynek w parze + porównania z mistrzami: $\sim \tfrac{3n}{2}$ zamiast $2n$.
• Lider i algorytm skreślania par — wartość > $n/2$ wystąpień; kandydat z licznikiem + obowiązkowa weryfikacja.
• Problem idola — każdy pytanie eliminuje osobę: kandydat w $n-1$ pytań + weryfikacja.

📌 Najważniejsze w pigułce

• Nie sortuj, gdy pytanie nie wymaga porządku — odpowiedź bywa o klasę tańsza.
• Skreślanie par nie zmienia lidera; kandydat bez weryfikacji to pół algorytmu i całe kłamstwo.
• Wspólna dusza: każda odpowiedź musi trwale zmniejszać pole gry.

🎒 Zadania

1. Ile porównań wykona min_max dla $n = 8$, a ile podejście naiwne? Rozpisz rachunek z kodu (pierwsza para + trzy na każdą kolejną).

Wskazówka i odpowiedź

Start parą: 1 porównanie. Pozostałe 3 pary: po 3 porównania = 9. Razem 10; naiwnie $2 \cdot 8 - 2 = 14$ (no, $2n-3$ = 13 przy sprytnym starcie). Wzór ogólny: $\lceil \tfrac{3n}{2} \rceil - 2$ — dla ośmiu: 10 ✓. Udowodniono, że mniej się nie da — kolejny (trzeci już w tym dziale!) wynik „to jest dno": min-max ma swoją dolną granicę jak sortowanie.

2. Wybory klasowe: 30 głosów w liście. Kiedy lider zwróci przewodniczącego, a kiedy None — i czy „zwycięzca zwykłą większością" (najwięcej głosów, ale ≤ 15) jest do znalezienia tym algorytmem? Jak go znaleźć?

Wskazówka i odpowiedź

lider żąda > 15 głosów — bezwzględnej większości; przy trzech kandydatach po 12/10/8 zwróci None, choć zwycięzca istnieje. Zwykła większość (moda, wartość najczęstsza) wymaga innego narzędzia: zliczania wszystkich wartości (tablica/tablica haszująca liczników — dział 9) albo posortowania i policzenia serii. Skreślanie par działa TYLKO dla większości bezwzględnej — bo tylko wtedy „para różnych" na pewno zawiera co najwyżej jeden głos lidera. Znaj granice swoich algorytmów równie dobrze, jak ich moc.

3. W problemie idola macierz znajomości ma $n^2$ pól, a algorytm zadaje ~$3n$ pytań — czyli nie czyta większości danych. Czy to nie łamie dolnej granicy z 6.1 („trzeba obejrzeć wszystko")? Rozstrzygnij pozorny paradoks.

Wskazówka i odpowiedź

Granica z 6.1 dotyczyła pytania, na które każdy nieobejrzany element mógł wpłynąć. Tu struktura odpowiedzi jest mocniejsza: jedno „A zna B" logicznie wyklucza całą osobę — a wraz z nią $2n$ pól macierzy, których czytać już nie trzeba. Dolne granice zależą od problemu, nie od rozmiaru danych: gdy odpowiedzi niosą skorelowaną informację, wolno „nie przeczytać" większości wejścia. Idol jest ulubionym kontrprzykładem wykładowców na zbyt pochopne „przecież trzeba wszystko obejrzeć".

🔍 Sprawdź, czy umiesz

• Policzyć min i max metodą par z rachunkiem porównań.
• Wykonać algorytm lidera z weryfikacją — i wyjaśnić, czemu bez niej kłamie.
• Opowiedzieć eliminację idola i wskazać wspólną zasadę wszystkich trzech algorytmów.