Algoritmy: třídění, hledání a Big-O

Co tento kvíz pokrývá

Od bublinkového třídění vs. quicksort po binární vyhledávání a asymptotickou notaci, tento kvíz cílí na základní myšlenky za výkonem a správností algoritmů.

Každá otázka má 4 možnosti a není zde časovač, takže můžete zpomalit, spočítat a vybudovat spolehlivou intuici místo toho, abyste spěchali.

Dovednosti, které budete procvičovat

Budete procvičovat čtení popisů podobných pseudokódu, odhadování doby běhu a výběr správného přístupu pro dané omezení (seřazený vstup, omezení paměti, duplicity, chování v nejhorším případě).

Běžné nástrahy zahrnují zaměňování průměrného a nejhoršího případu, předpokládání, že binární vyhledávání funguje na neuspořádaných datech, a zacházení s Big-O jako s přesným časem běhu místo míry růstu.

Obtížnost a jak hrát

Obtížnost je smíšená záměrně: jednodušší položky posilují definice a standardní složitosti, zatímco těžší vás tlačí k porovnávání obchodních kompromisů a uvažování o okrajových případech. Vyberte si počet otázek a obtížnost před začátkem, abyste přizpůsobili sezení - použijte kratší běhy pro rychlé přezkoušení nebo delší běhy pro budování výdrže.

• Identifikujte Big-O (a někdy Big-Theta) běžných smyček a rekurzí
• Porovnejte algoritmy třídění podle stability, chování na místě a typického výkonu
• Rozhodněte, kdy lineární vyhledávání poráží binární vyhledávání v reálných omezeních
• Odhalujte chyby o jeden a problémy s hranicemi v logice vyhledávání
• Interpretujte nejlepší/průměrné/nejhorší scénáře, aniž byste je zaměňovali
• Spojte omezení problému s volbou algoritmu (kompromisy mezi časem a prostorem)