Big-O pre základné operácie

Čo budete cvičiť

Big-O pre základné operácie je miesto, kde sa príprava na pohovor stretáva s reálnym programovaním: vloženie, vymazanie, vyhľadávanie, prístup, prechádzanie a zmenšovanie cez polia, prepojené zoznamy, zásobníky, fronty, hash tabuľky, haldy a stromy.

Každá otázka používa 4 možnosti a nie je tu časovač, takže sa môžete spomaliť a premýšľať o najlepších/priemerných/najhorších prípadoch bez tlaku.

Ako sú vyvážené obtiažnosť a dĺžka

Kvíz je navrhnutý ako zmiešaná obtiažnosť: dostanete zmes rýchlych výhier (ako O(1) prístupové vzory) a zložitejších porovnaní (ako amortizované vs najhorší prípad). Vyberte si počet otázok a obtiažnosť pred začatím—krátke sady na rozcvičku, dlhšie behy na vytrvalosť a zapamätanie si.

Bežné pasce, ktorým sa treba vyhnúť

Mnohé nesprávne odpovede prichádzajú z miešania priemerného vs najhoršieho prípadu, zabúdania na amortizované náklady (dynamické polia, prehashovanie hash tabuliek) alebo predpokladania "zoradené" bez toho, aby to bolo povedané.

Dávajte pozor na skryté kroky ako prechádzanie pred vymazaním, spracovanie kolízií a či operácia potrebuje posun alebo prelinkovanie.

Tipy na dosiahnutie vyššieho skóre

• Oddelujte časovú vs priestorovú zložitost', keď premýšľate o operácii
• Pýtajte sa sami seba: vyžaduje to skenovanie, posun, vyváženie alebo zmenšovanie?
• Pamätajte na amortizovanú analýzu pre dynamické polia a hash tabuľky
• Pre stromy skontrolujte, či je štruktúra vyvážená alebo môže degradovať
• Nepredpokladajte, že O(1) hashovanie znamená O(1) v najhoršom prípade