Algoritmas - tai veiksmų seka, pradinius duomenis paverčiančių rezultatais. Šis žodis kilo iš IX a. mokslininko Al-Khwarizmi vardo.
Taigi, kas gi yra spartus algoritmas? Tai algoritmas, kuris su minimaliomis pastangomis atlieka tai, ką turi atlikti. Algoritmas užrašomas realia programavimo kalba.
Reikėtų atskirai paminėti euristinius algoritmus. Tačiau rastasis sprendinys dažniausiai yra artimas ieškomajam, nors ir ne visada optimalus. Pavyzdžiui, kelis šimtmečius.
Atsižvelgiant į algoritmo efektyvumą, svarbu suprasti, kas yra algoritmo sudėtingumas, t. y. reikalingą laiką ir atminties išteklius, priklausomai nuo pradinių duomenų kiekio.
Pradinių duomenų dydis - tai, pavyzdžiui, rikiuojamų skaičių kiekis, bet ne patys skaičiai. Jį nusako funkcija .
Kiekvienos programos veikimą nusakys vis kitokia funkcija. Laimei, sudėtinga to daryti neteks!
Panagrinėkime kurį nors rikiavimo algoritmą. Elementarių veiksmų skaičius - . Jei auga kiekvienas iš dėmenų, pirmasis dėmuo, o kiti dėmenys - labai nežymiai, tai mažesniuosius dėmenis galime atmesti. Augančio funkcijos dėmens, t.y. nuo .
Algoritmo sudėtingumą nusako funkcija , kuri rodo, kaip didėja algoritmo atlikimo laikas didėjant pradiniams duomenims, t. y. duomenų dydžiui.
Jei algoritmas veikia nepriklausomai nuo pradinių duomenų dydžio (t. y. pastovus, konstantinis), tai jį žymėsime .
Pradinių duomenų dydį gali nusakyti ne vienas, o keli kintamieji - parametrams.
Efektyviais laikomi polinominio sudėtingumo algoritmai, t. y. kurių sudėtingumo funkcija yra polinomas - . Tai reiškia, kad algoritmas gali įveikti uždavinius su dideliais pradiniais duomenimis per leistiną laiką.
Beje, beveik visose programose 90% laiko sugaištama vykdant 10% kodo. Todėl kartais verta susitelkti į šių 10% kodo efektyvumą.
Kritiškai įvertinkime savo algoritmą. Tarkime, turime masyvą , , ir norime rasti sumą . Algoritmo sudėtingumas - . Tai nėra geriausias uždavinio sprendimo būdas.
Apibendrinant, efektyvumą būtina įvertinti, ypač sprendžiant sudėtingus kombinatorinių optimizavimo uždavinius.
NP (Nedeterminuotas polinominis) uždaviniai - tai uždavinių klasė, kuriai sprendimą per polinominį laiką galime patikrinti, ar sprendinys teisingas. Jei uždavinys priklauso NP klasei, ar tai blogai? Ne, nes jei žinome, kad pakaks ir neefektyvaus algoritmo uždaviniui spręsti.
Kaip veikia nauji YouTube algoritmai | Video marketingas - Atradau.lt
Pavyzdžiui, tokia formuluotė: ar duotas grafas turi Hamiltono ciklą (t. y. ciklą, einantį per visas viršūnes)? Ar šis uždavinys, jūsų žiniomis, yra NP pilnas? Tikrai neverta pulti į paniką, jei nežinote, nes jūs tai jau žinote!
K. Montonas buvo tikras, kad jo milijonas yra saugus, nes sprendimas užtruks ilgiau nei gyvuos Visata. Tačiau du Kembridžo matematikai A. Holmsas (Andrew Holmes) ir O. Riordanas (Oliver Riordan) sugebėjo sudėti dėlionę iki nurodytos datos. Jiems pavyko surasti sprendinį kompiuterių per porą savaičių.
Algoritmo sudėtingumo klasės
Ši lentelė padeda suprasti, kaip skirtingi sudėtingumo lygiai veikia algoritmo efektyvumą didėjant duomenų kiekiui:
| Sudėtingumo klasė | Aprašymas | Pavyzdys |
|---|---|---|
| O(1) | Pastovus sudėtingumas. Algoritmo vykdymo laikas nepriklauso nuo įvesties dydžio. | Prieiga prie elemento masyve pagal indeksą. |
| O(log n) | Logaritminis sudėtingumas. Algoritmo vykdymo laikas didėja logaritmiškai, didėjant įvesties dydžiui. | Dvejetainė paieška surūšiuotame masyve. |
| O(n) | Linijinis sudėtingumas. Algoritmo vykdymo laikas tiesiogiai priklauso nuo įvesties dydžio. | Paieška nesurūšiuotame masyve. |
| O(n log n) | Linijinis-logaritminis sudėtingumas. Algoritmo vykdymo laikas didėja beveik tiesiškai, bet šiek tiek greičiau nei tiesiškai. | Greitasis rikiavimas (QuickSort) ir suliejimo rikiavimas (MergeSort). |
| O(n^2) | Kvadratinis sudėtingumas. Algoritmo vykdymo laikas didėja kvadratu, didėjant įvesties dydžiui. | Burbulo rikiavimas (Bubble Sort) ir įterpimo rikiavimas (Insertion Sort). |
| O(2^n) | Eksponentinis sudėtingumas. Algoritmo vykdymo laikas didėja eksponentiškai, didėjant įvesties dydžiui. | Visų galimų poaibių generavimas. |
| O(n!) | Faktorinis sudėtingumas. Algoritmo vykdymo laikas didėja labai greitai, didėjant įvesties dydžiui. | Visų galimų permutacijų generavimas. |
Šią lentelę verta įsidėmėti, kad suprastumėte, kaip skirtingi algoritmai veikia esant skirtingiems pradiniams duomenims.
Algoritmai ir Naratyvai Teksto Analizėje
Naratyvas yra istorijos ar pasakojimo struktūra, kuri padeda suvokti ir interpretuoti informaciją. Algoritmas yra sekos žingsnių ar taisyklių rinkinys, kuris naudojamas duomenų analizėje ir apdorojime. Naratyvas ir algoritmas gali būti naudojami kartu siekiant gilesnio teksto supratimo.
Naratyvas yra daugiau susijęs su teksto struktūra, istorija ir kontekstu, tuo tarpu algoritmas yra daugiau susijęs su duomenų apdorojimu ir analize. Naratyvas gali padėti suvokti teksto kontekstą ir svarbias temas, tuo tarpu algoritmai gali padėti išgryninti svarbius žodžius, ryšius ar tendencijas tekste.
Supratimas apie algoritmus yra būtinas norint efektyviai naudoti šiuolaikines technologijas ir spręsti įvairias problemas.
tags: #as #noriu #buti #tikras #algoritmas