Santa Claus — modified 2022-03-12 23:16 (298 days ago) — edit — reply
Graf (matici) projdeme tímto způsobem: Projdeme indexy 1 až n a pamatujeme si **aktuálně sledovaného kandidáta** a **nejnižšího následujícího kandidáta**, na začátku to jsou první a druhý vrchol. Vždy se podíváme na to, jaká hrana vede mezi dvěma sledovanými vrcholy. + Pokud vede hrana do aktuálního kandidáta, už není kandidátem (protože z něj nevede hrana), aktuálním kandidátem se stává nejnižší následující kandidát a nový nejnižšího následující kandidát bude následující vrchol, pokud existuje. + Pokud vede hrana z aktuálního kandidáta, pak zůstává kandidátem a nový nejnižší kandidát se posune o index dál (ho zavrhneme, protože z něj nevede hrana), pokud takový existuje. + Pokud mezi nimi hrana nevede, oba ztrácejí status kandidáta (protože nevede hrana z jednoho do druhého) a novými kandidáty se stávají postupně vrcholy s indexy o jedna a dva vyšší než nejnižší následující, pokud neexistuje vrchol s indexem o dva vyšší, určí se pouze poslední kandidát. Pokud neexistuje ani vrchol s indexem o jedna nižší, šéf neexistuje. V rámci prvního průchodu platí tyto invarianty: + V každém kroku jsou všechny vrcholy před aktuálním kandidátem zavrhnuty, + Taktéž jsou zavrhnuty všechny vrcholy mezi kandidátem a nejnižším následujícím kandidátem, + O vrcholech vyššího indexu zatím nic nevíme. Povšimněme si, že po průchodu všemi indexy zbyde pouze jediný kandidát - ať už poslední porovnání vyjde jakkoliv ze tří možností, vždy zbyde jediný kandidát dle daných instrukcí. U něj u stačí ověřit, jestli je opravdu šéfem, v druhém průchodu - prostě prozkoumáme odpovídající řádek. První průchod zabere $n$ iterací o konstantním čase, druhý průchod až $n$ porovnání, celkem tedy $n + n \in O(n)$, což je oproti rozměru matice $n^2$ lepší než lineární. Lépe už to jít nemůže, protože musíme zkontrolovat alespoň $n$ vrcholů případného šéfa.