Ak
Rozsah
Aj keď ma odpoveď zaujíma, skôr ma zaujíma, ako nájsť odpoveď krok za krokom (aby som mohol tento postup zopakovať a porovnať všetky dva zadané algoritmy, pokiaľ je to možné).
Z knihy MIT Press Algorithms
odpovede:
3 pre odpoveď č. 1To je ľahké. Chceš hodnoty n kde 100* n ^ 2 je menej než 2n.
Čo je riešením 100n^2 - 2n < 0, čo sa náhodou stáva
0 < n < 0.02.
Tisíc slov:
2 pre odpoveď č. 2
Prvá vec, ktorú musíte vedieť, je, čo bežíčas znamená. Ak teoreticky hovoríme o algoritmoch, doba trvania algoritmu je počet krokov (alebo množstvo času) potrebných na dokončenie. v závislosti od veľkosti vstupu (kde veľkosť vstupu je napríklad počet bitov, ale niekedy sa zvažujú aj iné miery). V tomto zmysle je algoritmus, ktorý vyžaduje najmenší počet krokov, najrýchlejší.
Takže vo vašich dvoch vzorcoch je n veľkosť vstupu a 100 * n ^ 2 a 2 ^ n predstavuje počet krokov, ktoré dva algoritmy spustia, ak dostanú vstup veľkosti n.
Na prvý pohľad vyzerá algoritmus 2 ^ n oveľa rýchlejšie ako algoritmus 100 * n ^ 2. Napríklad pre n = 4, 100 * 4 ^ 2 = 1600 a 2 ^ 4 = 16.
Avšak 2 ^ n je exponenciálna funkcia, zatiaľ čo 100 * n ^ 2 je a polynomiálna funkcia. To znamená, že keď je n dostatočne veľké, bude tobyť prípad, že 2 ^ n> 100 * n ^ 2. Nerovnosť teda budete musieť vyriešiť 100 * n ^ 2 <2 ^ n. Toto už bude platiť pre pomerne malé n, takže môžete začať hodnotiť funkcie od n = 5 a k odpovedi na otázku sa dostanete za pár minút.