Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Porozumieť časovej zložitosti a zložitosti vesmíru:
* Čas zložitosť: Meria čas, ktorý algoritmus potrebuje na dokončenie ako funkcia veľkosti vstupu (často označovaná ako „n“). Zaujímajú sa o * ako * čas vykonávania rastie, nie presný čas v sekundách.
* Vesmírna zložitosť: Meria množstvo pamäte (alebo priestoru), ktorý algoritmus vyžaduje ako funkciu veľkosti vstupu „n“. Zahŕňa to priestor pre vstupné údaje a všetky pomocné dátové štruktúry používané algoritmom.
2. Identifikácia kľúčových operácií:
* Základné operácie: Identifikujte operácie, ktoré významne prispievajú k času vykonávania. To by mohlo zahŕňať:
* Aritmetické operácie (+, -, \*, /, %)
* Porovnania (<,>, ==,! =)
* Priradenia (=)
* Prístupy poľa (ARR [i])
* Prideľovanie pamäte a deachácie (v závislosti od jazyka)
* Zamerajte sa na dominantné operácie: Niektoré operácie sa vykonávajú oveľa častejšie ako iné. Zamerajte sa na tieto * dominantné * operácie, pretože budú mať najväčší vplyv na celkový beh. Napríklad v algoritme triedenia sú porovnania a swapy dominantné.
3. Analyzujte štruktúru algoritmu (návod na kód):
* sekvenčné výroky: Vyhlásenia vykonané postupne prispievajú k konštantnému času alebo priestoru.
* slučky: Časová zložitosť slučky závisí od toho, koľkokrát iteruje:
* Simple Loop (Linear): „Pre i v rozsahu (n):...` vykonáva 'n' krát, takže zložitosť je o (n).
* vnorené slučky (kvadratické, kubické atď.): `Pre i v rozsahu (n):pre j v rozsahu (n):...` vykonáva 'n * n' times, takže zložitosť je o (n^2).
* slučka s logaritmickým správaním: `Zatiaľ čo n> 1:n =n // 2` vykonáva časy log2 (n), takže zložitosť je o (log n).
* slučka so závislosťou od vnútornej logiky: Analyzujte telo slučky, aby ste určili jej zložitosť a vynásobte ju počtom iterácií.
* Podmienené príkazy (ak/else):
* Analyzujte bloky `if` a` else ". Celková zložitosť je * maximálna * zložitosť blokov „if“ a `else`.
* Pre hlboko vnorené `if/else` štruktúry, opatrne sledujte možné cesty vykonávania.
* rekurzia:
* Identifikujte základné prípady: Tieto ukončia rekurziu.
* Identifikujte rekurzívny krok: Ako sa problém rozdelí na menšie podprava.
* Napíšte vzťah recidívy: To matematicky popisuje časovú zložitosť rekurzívnej funkcie. Napríklad:`t (n) =t (n/2) + o (1)` (binárne vyhľadávanie)
* Vyriešte vzťah recidívy: Na nájdenie asymptotickej časovej zložitosti používajte metódy, ako je hlavná veta, substitúcia alebo strom rekurzie.
* Funkčné volanie: Zvážte časovú zložitosť volanej funkcie. Ak funkcia „A` volá funkciu` B`, časová zložitosť `A` bude obsahovať časovú zložitosť` B`.
4. Vyjadrite zložitosť v asymptotickom notácii (Big O, Big Omega, Big Theta):
* Big O notácia (o): Predstavuje * hornú hranicu * rýchlosti rastu algoritmu. Opisuje * najhorší scenár *. „Časová zložitosť algoritmu je O (n^2)“ znamená, že runtime algoritmu nebude rásť * rýchlejšie * ako n^2, keď sa zvyšuje 'n'.
* Big Omega Nottion (Ω): Predstavuje * dolnú hranicu * rýchlosti rastu algoritmu. Opisuje * najlepší prípad * scenár. „Časová zložitosť algoritmu je Ω (n)“ znamená, že runtime algoritmu nebude rásť * pomalšie * ako 'n', ako sa zvyšuje 'n'.
* Big theta Netration (θ): Predstavuje * tesnú hranicu * rýchlosti rastu algoritmu. Opisuje scenár priemerného prípadu a keď runtime algoritmu rastie rovnakou rýchlosťou ako funkcia. „Časová zložitosť algoritmu je 9 (n log n)“ znamená, že runtime algoritmu bude rásť rovnakou rýchlosťou ako n log n.
Spoločné časové zložitosti (najhorší prípad, veľký o):
* o (1):Konštantný čas: Čas vykonávania je nezávislý od veľkosti vstupu. Príklad:Prístup k prvku v poli podľa jeho indexu.
* o (log n):logaritmický čas: Čas vykonávania sa zvyšuje logaritmicky s veľkosťou vstupu. Príklad:Binárne vyhľadávanie v zoradenom poli.
* o (n):lineárny čas: Čas vykonávania sa s veľkosťou vstupu lineárne zvyšuje. Príklad:Hľadanie prvku v netriedenom poli.
* o (n log n):linearitmický čas: Bežné v efektívnych triediacich algoritmoch. Príklad:Zlúčiť zoradenie, Quicksort (priemerný prípad).
* o (n^2):kvadratický čas: Čas vykonávania sa zvyšuje kvadraticky s veľkosťou vstupu. Príklad:triedenie bubliny, triedenie vloženia.
* o (n^3):kubický čas: Príklad:Násobenie matíc.
* o (2^n):exponenciálny čas: Čas vykonávania sa zdvojnásobí pri každom pridaní k veľkosti vstupu. Často naznačuje prístup k brutálnej sile. Príklad:Vyskúšajte všetky možné podskupiny súboru.
* o (n!):faktorový čas: Čas vykonávania rastie mimoriadne rýchlo. Príklad:Nájdenie všetkých permutácií súboru.
5. Ignorujte konštantné faktory a výrazy nižšieho poriadku:
Pri použití asymptotického notácie sa zaujímame predovšetkým o dominantný * termín, ktorý určuje mieru rastu. Konštantné faktory a výrazy nižšieho poriadku sa stávajú zanedbateľnými, pretože „N“ rastie veľmi veľké.
* `3n^2 + 5n + 10` je zjednodušený na` o (n^2) `
* `100 log n + n` je zjednodušený na` o (n) `(n rastie rýchlejšie ako log n)
* `2^n + n^5` je zjednodušený na` o (2^n) `
6. Analyzujte zložitosť priestoru:
Podobne ako v časovej zložitosti analyzujte priestor používaný algoritmom. Zvážte:
* Vstupný priestor: Priestor potrebný na uloženie vstupných údajov.
* pomocný priestor: Extra priestor, ktorý používa algoritmus, za vstupným priestorom, pre premenné, dátové štruktúry a zásobník hovorov rekurzie.
Príklady:
* lineárne vyhľadávanie:
`` `Python
def linear_search (ARR, cieľ):
pre i v rozsahu (Len (ARR)):
Ak ARR [i] ==cieľ:
vrátiť i
návrat -1
`` `
* Čas zložitosť: O (n) (lineárny, najhorší prípad:Target nie je v poli alebo je posledným prvkom)
* Vesmírna zložitosť: O (1) (konštantné, pretože používa iba niekoľko ďalších premenných)
* binárne vyhľadávanie:
`` `Python
def binary_search (ARR, cieľ):
nízko =0
vysoký =len (arr) - 1
zatiaľ čo nízka <=vysoká:
mid =(nízka + vysoká) // 2
Ak ARR [mid] ==cieľ:
v polovici
Elif ARR [MID]
inak:
vysoký =stredný - 1
návrat -1
`` `
* Čas zložitosť: O (log n) (logaritmické)
* Vesmírna zložitosť: O (1) (konštantná, iteračná verzia)
* Rekurzívne binárne vyhľadávanie:
`` `Python
def binary_search_recursive (ARR, cieľ, nízka, vysoká):
Ak nízko> vysoká:
návrat -1
mid =(nízka + vysoká) // 2
Ak ARR [mid] ==cieľ:
v polovici
Elif ARR [MID]
inak:
return binary_search_recursive (ARR, cieľ, nízka, stredná - 1)
`` `
* Čas zložitosť: O (log n)
* Vesmírna zložitosť: O (log n) v dôsledku hĺbky rekurzie. Každý rekurzívny hovor pridá do zásobníka hovorov nový rám.
v súhrne:
1. Definujte, čo chcete zmerať: Časová zložitosť, zložitosť vesmíru alebo oboje.
2. Identifikujte kľúčové operácie prispievanie k využitiu zdrojov.
3. Analyzujte štruktúru algoritmu (slučky, podmienky, rekurzia).
4. vyjadruje zložitosť Používanie Big O, Big Omega alebo Big theta Notácie.
5. Ignorujte konštantné faktory a výrazy nižšieho poriadku.
Podľa týchto krokov môžete efektívne analyzovať účinnosť algoritmov a zvoliť najvhodnejší algoritmus pre vaše konkrétne potreby. Pamätajte, že najlepší algoritmus závisí od konkrétneho problému, veľkosti vstupných údajov a dostupných zdrojov.