Az algoritmus hatékonysága

Itt egy jelentés, amiben az áll hogy egy új marsjárót küldenek a Marsra. A mi felelősségünk az, hogy elkészítsük annak az algoritmusnak a programját, amely a marsjáróban ellenőrzi, hogy egy szám prímszám-e. Tegyük fel, hogy a marsjáró RSA-t használ a kommunikációhoz. Kell egy algoritmus a prímszám ellenőrzéshez. Most ... amikor egy marsjárót, vagy bármilyen űrkütyüt tervezel, minden tekintetben nagyon hatékonynak kell lenned. A felhasznált alkatrészeknek nagyon könnyűeknek kell lenniük. Az alrendszerek által használt energiát a minimálisra kell szorítani. A tervezés minden szakaszában energiát és tömeget kell megtakarítani. Ez itt a számunkra kijelölt munka. Ez a maximális érték, amit tudni kell kezelni, és mindezt nagyon gyorsan. Ha egy nagyon kis bemenetet kap, mondjuk 90-et, akkor majdnem olyan gyorsan kell megkapni az eredményt, mintha ezt az egész számot adnánk meg. Ahogy nő a bemenet értéke, nem akarunk észrevehető teljesítmény-csökkenést látni. Vizsgáljuk meg a felhasználók által feltett nagyon jó kérdéseket matematikai szempontból! Azt vizsgáljuk, hogy n prímszám vagy összetett szám-e. Ha adva van egy n szám, legyen ez az összes lehetséges n-ek halmaza. Ha n = 100, ez a tér 2-től 100-ig tart. A mi algoritmusunk ebben a térben keres. Gondolj egy algoritmusra, ami egy adott térben keres. Minden ponton feltesz egy kérdést. Úgy képzeld el, ez egy lépés, egy egyszerű lépés. Feltesz egy kérdést, ami most egy oszthatósági próba, ez a kérdés. Tegyük fel, ez a szám 'a', akkor az oszthatósági próba metódusban a feltett kérdés: „n osztható a-val?” Egyszerűen kipróbáljuk, ide tesszük a-t, és megpróbáljuk n-et elosztani a-val, és megnézzük, vajon 0-e a maradék, vagyis 'a' osztója-e n-nek, és azt mondhatjuk, most 100%-ig biztosak vagyunk... Felemelhetjük a zászlót, 100%-ig biztosak vagyunk abban, hogy összetett szám. Egyébként a többi lépésnél nem tudjuk biztosan. Talán prímszám, de nem vagyunk benne biztosak. Úgyhogy tovább keresünk, amíg el nem jutunk a végére. Ne feledd, a fal ebben az esetben n négyzetgyöke. A legrosszabb eset az, amikor n prímszám, ekkor a keresést egészen n négyzetgyökéig folytatni kell, és csak ekkor mondhatjuk azt, hogy prímszám, és ebben 100%-ig biztosak vagyunk. Abban az esetben, ha n két prím szorzata, 7 · 7= 49. Ha 49-et adunk meg az algoritmusunknak, a legrosszabb eset fordul elő. Egészen n négyzetgyökéig kell elmennünk. Ez volt a kérdések egyik részében, például TheFourthDimension kérdése: „Ha egyszer kizártuk 2-t, mint lehetséges osztót, akkor a 2 összes többszöröse kizárható, és ugyanez igaz 3-ra, 4-re, 5-re stb.” Ez egy jó meglátás. A régi algoritmus egyesével lépkedett. Felhasználhatjuk az összetett számok mintázatával kapcsolatos tudásunkat, mint például, ha egy szám osztható 2-vel, akkor az összetett. Ha nagyobb, mint 2, mert a 2 prímszám, akkor tudjuk, hogy 4 összetett. Ohh, ... bocs, kihagytam az 5-öt. 4, 6, 8, 10, ehelyett itt így lépkedhetünk: 3, 5, 7, 9. A hozzászólások egyik típusa ezt a teret akarja leszűkíteni. Ha kihagyjuk az összes páros számot, akkor a vizsgálati tér nem négyzetgyök n méretű, hanem négyzetgyök n per 2. Más mintát is találunk az összetett számoknál, hogy tovább csökkentsük a teret. A hozzászólások másik típusa azokat az eseteket érinti, amikor összetett számmal találkozunk. Azaz ha olyan a-t találunk, ami alapján azt mondhatjuk: „Ó, biztosan tudjuk, hogy n összetett.” Lola azt kérdezte: „Ha kiugranánk a ciklusból, amint primeCheck hamis, nem csökkentené le a keresési időt?” Igen, ez teljesen igaz, és ezt is fogjuk tenni. A keresés bármely lépésénél, akármelyik mintát követjük, ha összetett számra találunk bizonyítékot. Ez azt jelenti, hogy átmegy a teszten, és 100%-os biztonsággal előbb megállhatunk. Kiszállunk, és azt mondjuk: „Kész vagyunk. Nem keresünk tovább.” Ez a korai kiszállás nagyon jó, kivéve, hogy a legrosszabb esetben, ami az, hogy ha n prímszám, nem segít a korai kiszállás. Most nézzük meg, hogyan szűkítik ezek a javítások a teret, lecsökkentve a számítógépben elvégzendő ellenőrzések számát, ami a használt számítógéptől függően lecsökkenti a szükséges időt. Készítettem egy szemléltető példát, ami összehasonlít két algoritmust annak alapján, hogy a végrehajtás során hány lépést hajt végre. A bal oldal mutatja az A algoritmust, a próbálkozásos osztást, ami 2-től gyök n-ig mindent végigpróbál. Jobb oldalt van a B algoritmus, nevezzük ezt a javított algoritmusnak. Itt beiktattam a vizsgálatot, hogy osztható-e 2-vel, így csak feleannyi lépés kell. A B algoritmusban korai kiszállás is van. Nem tökéletes, de beiktattam néhány javítást. Így megnézhetjük, mi történik. Egy kicsit eljátszogatok, hogy megmutassam. Ahogy ezt itt görgetem, látjuk az A algoritmust. Itt a kimenet, hogy összetett-e vagy prímszám. Itt alul látszik a lépések száma. Az első, amit látunk, az az, hogy a jobb oldalon minden második számhoz elég egy lépés. Tudjuk, ez miért van. Ha páros a szám, mint ez is, kilépünk. A régi algoritmusnak 314 lépés kellett. Az új algoritmusnak elég volt egy lépés, mert megvizsgálta, hogy osztható-e 2-vel. Ez egy igen jó optimalizációnak tűnik. De ahogy nő a bemenet, látszik, hogy a lépések száma emelkedik, az oszlop nő és pirosra válik, amint megközelítjük azt a sávot, ahol összeomlik. Ez a piros vonal a lépéshatár. Ha az oszlop eléri ezt, sikertelenek leszünk, a marsjáró elromlik. Ebben az esetben a böngésző lefagy. Megpróbálom megközelíteni. Már közel vagyok, nagyon lelassult. Érződik, hogy a böngésző a lefagyás közelébe került és meg fog halni. Figyeld meg, hogy a javított algoritmusnak csak két lépés kellett ebben az esetben, de ne felejtkezz el a legrosszabb esetről. Van itt nekem elmentve néhány nagy prímszám a példához. Minden esetet kezelni kell tudni. Nem tudjuk, mit kap az algoritmus. Ha beadunk egy nagy prímszámot, nézd meg, mi történik. A B algoritmusnak, tudjuk, feleannyi lépésre van szüksége a legrosszabb esetben, de még így is sok lépése van, mert ez a legrosszabb eset, ugye. Egyre közelebb kerülünk a lefagyáshoz, és ez még csak nem is egy nagyon nagy prím. Még jóval 15 számjegy alatt vagyunk. Ha beadom ezt a 12 számjegyű számot az algoritmusnak, nézzük, mi történik. Lelassult, le fog fagyni. Nézd, mindkét algoritmus jóval meghaladta a küszöböt. Nem működött. A javított algoritmus még nem elég jó. De most már értjük, min szeretnénk javítani, a legrosszabb esetben szükséges lépések számán. Van nekünk ez a jó kis eszközünk, amivel láthatjuk a növekedést, hogyan emelkedik a szükséges lépések száma a bemenet növekedésével. A következőkben el fogom magyarázni, hogyan építettem ezt fel, úgyhogy elkészítheted a saját algoritmusodat, összehasonlíthatod az alapesettel, és eldöntheted, te mennyivel tudsz jobbat csinálni.