Azərbaycan
Deutschland
Lietuva
Malta
ශ්රී ලංකාව
Türkmenistan
Türkiyə
Украина
Šį straipsnį yra pasiūlyta sujungti su Rikiavimo algoritmas Dėl kokių priežasčių palikta ši žymė galite sužinoti diskusi
Rikiavimo algoritmų sudėtingumas
| Šį straipsnį yra pasiūlyta sujungti su „Rikiavimo algoritmas“. Dėl kokių priežasčių palikta ši žymė, galite sužinoti diskusijų puslapyje. |
Dažnai greitam darbui su duomenimis būtina duomenis surikiuoti, bet esant dideliems duomenų kiekiams labai svarbu ir paties rikiavimo algoritmo sudėtingumas – atlikimo greičio priklausomybė nuo duomenų kiekio.
Duomenų rikiavimo uždavinys apibrėžiamas taip:
- Turint N elementų seką (a1, a2, …, aN), reikia išdėstyti šiuos elementus taip, kad gautume naują N elementų seką (a1', a2', …, aN'), tenkinančią salygą ai <= aj, kai i<j.
Problematika
Algoritmų analizėje duomenų rikiavimo problema laikoma pačia svarbiausia, nes tai viena dažniausiai pasitaikančių operacijų programavime. Efektyvus rikiavimo algoritmo pasirinkimas gali turėti netgi lemiamą įtaką programos vykdymo spartai didėjant duomenų kiekiui.
Paprasčiausių rikiavimo algoritmų (išrinkimo rikiavimo algoritmas, įterpimo rikiavimo algoritmas, burbulo metodas) sudėtingumas yra kvadratinis (žymima O(N²). Dažnai greičiausiu laikomo greitojo rikiavimo (quicksort) algoritmo sudėtingumas daugeliu atveju yra O(N log N), tačiau rikiuojant beveik surikiuotus duomenis, šio algoritmo sudėtingumas siekia O(N²).
Algoritmo sudėtingumas svarbus tik esant dideliam duomenų kiekiui. Palyginimui pateikiama lentelė kaip skiriasi procesoriaus operacijų skaičius didėjant duomenų kiekiui, naudojant du skirtingus algoritmus – pirmasis naudoja 5 N² operacijų, o antrasis – 20 N log N.
| Duomenų elementų skaičius | Santykinis laikas burbulo algoritmu | Santykinis laikas quicksort algoritmu |
|---|---|---|
| 10 | 500 | 200 |
| 100 | 50 000 | 4 000 |
| 1000 | 5 000 000 | 60 000 |
| 10000 | 500 000 000 | 800 000 |
Jei duomenų kiekis nedidelis, mums dažniausiai visiškai nesvarbu, kiek mikrosekundžių bus vykdomas rikiavimas, tačiau esant didesniems duomenų kiekiams šis skirtumas yra milžiniškas. Kita vertus, esant labai mažiems duomenų kiekiams efektyvesnis bus burbuliuko metodas. Taip pat algoritmų sudėtingumas priklauso nuo duomenų savybių. Pavyzdžiui, burbuliuko metodas bus daug greitesnis, jei bus bandoma rikiuoti surikiuotus duomenis – tada jo sudėtingumas yra O(n).
Dažniausiai matuojamas algoritmų sudėtingumas vidutiniu atveju, dažnai blogiausiu atveju ir tik kartais – geriausiu. Tas pats algoritmas, būdamas labai greitas geriausiu atveju, gali būti labai blogas vidutiniu ar blogiausiu atveju.
Pagrindiniai algoritmų kursuose pateikiami rikiavimo algoritmai ir jų sudėtingumas (vertinant palyginimo operacijų atžvilgiu):
Algoritmų sudėtingumų lentelė
| Algoritmas | Blogiausias | Vidutinis | Geriausias | Pastabos |
|---|---|---|---|---|
| Skaitmeninis radixsort | O(2d N) | O(2d N) | O(2d N) | Tik skaitmeninėms teigiamoms duomenų reikšmėms, kur d yra skaitmenų sk. Reikalauja papildomos atminties |
| Greitojo rikiavimo (quicksort) | O(N²) | O(N log N) | O(N log N) | Beveik nenaudoja papildomos atminties |
| Kombinuotas | O(N log N) | O(N (log N)²) | ||
| Krūvos (heapsort) | O(N log N) | O(N log N) | O (N log N) | |
| Šelo (Shell sort) | O(N²) | O(N1,2) | O(N) | |
| Sąlajos (mergesort) | O(N log N) | O(N log N) | O(N log N) | Stabilus, naudoja papildomą atmintį. Tinka kai nevisus duomenis iškarto galime nuskaityti į operatyvią atmintį |
| Burbulo (bubble) | O(N²) | O(N²) | O(N) | |
| Įterpimo (insertion) | O(N²) | O (N²) | O(N) | |
| Išrinkimo (selection) | O(N²) | O(N²) | O(N²) |
Lygiagretieji algoritmai
Naudojant daugiaprocesorinį kompiuterį ar paskirstytą kompiuterių tinklą galima pasiekti ir dar geresnių rezultatų. Geriausiu atveju pasiekiamas sudėtingumas O((log N)²).
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Rikiavimo algoritmų sudėtingumas, Kas yra Rikiavimo algoritmų sudėtingumas? Ką reiškia Rikiavimo algoritmų sudėtingumas?
Sį straipsnį yra pasiulyta sujungti su Rikiavimo algoritmas Del kokiu priezasciu palikta si zyme galite suzinoti diskusiju puslapyje Daznai greitam darbui su duomenimis butina duomenis surikiuoti bet esant dideliems duomenu kiekiams labai svarbu ir paties rikiavimo algoritmo sudetingumas atlikimo greicio priklausomybe nuo duomenu kiekio Duomenu rikiavimo uzdavinys apibreziamas taip Turint N elementu seka a1 a2 aN reikia isdestyti siuos elementus taip kad gautume nauja N elementu seka a1 a2 aN tenkinancia salyga ai lt aj kai i lt j ProblematikaAlgoritmu analizeje duomenu rikiavimo problema laikoma pacia svarbiausia nes tai viena dazniausiai pasitaikanciu operaciju programavime Efektyvus rikiavimo algoritmo pasirinkimas gali tureti netgi lemiama įtaka programos vykdymo spartai didejant duomenu kiekiui Paprasciausiu rikiavimo algoritmu isrinkimo rikiavimo algoritmas įterpimo rikiavimo algoritmas burbulo metodas sudetingumas yra kvadratinis zymima O N Daznai greiciausiu laikomo greitojo rikiavimo quicksort algoritmo sudetingumas daugeliu atveju yra O N log N taciau rikiuojant beveik surikiuotus duomenis sio algoritmo sudetingumas siekia O N Algoritmo sudetingumas svarbus tik esant dideliam duomenu kiekiui Palyginimui pateikiama lentele kaip skiriasi procesoriaus operaciju skaicius didejant duomenu kiekiui naudojant du skirtingus algoritmus pirmasis naudoja 5 N operaciju o antrasis 20 N log N Duomenu elementu skaicius Santykinis laikas burbulo algoritmu Santykinis laikas quicksort algoritmu10 500 200100 50 000 4 0001000 5 000 000 60 00010000 500 000 000 800 000 Jei duomenu kiekis nedidelis mums dazniausiai visiskai nesvarbu kiek mikrosekundziu bus vykdomas rikiavimas taciau esant didesniems duomenu kiekiams sis skirtumas yra milziniskas Kita vertus esant labai maziems duomenu kiekiams efektyvesnis bus burbuliuko metodas Taip pat algoritmu sudetingumas priklauso nuo duomenu savybiu Pavyzdziui burbuliuko metodas bus daug greitesnis jei bus bandoma rikiuoti surikiuotus duomenis tada jo sudetingumas yra O n Dazniausiai matuojamas algoritmu sudetingumas vidutiniu atveju daznai blogiausiu atveju ir tik kartais geriausiu Tas pats algoritmas budamas labai greitas geriausiu atveju gali buti labai blogas vidutiniu ar blogiausiu atveju Pagrindiniai algoritmu kursuose pateikiami rikiavimo algoritmai ir ju sudetingumas vertinant palyginimo operaciju atzvilgiu Algoritmu sudetingumu lenteleAlgoritmas Blogiausias Vidutinis Geriausias PastabosSkaitmeninis radixsort O 2d N O 2d N O 2d N Tik skaitmeninems teigiamoms duomenu reiksmems kur d yra skaitmenu sk Reikalauja papildomos atmintiesGreitojo rikiavimo quicksort O N O N log N O N log N Beveik nenaudoja papildomos atmintiesKombinuotas O N log N O N log N Kruvos heapsort O N log N O N log N O N log N Selo Shell sort O N O N1 2 O N Salajos mergesort O N log N O N log N O N log N Stabilus naudoja papildoma atmintį Tinka kai nevisus duomenis iskarto galime nuskaityti į operatyvia atmintįBurbulo bubble O N O N O N Įterpimo insertion O N O N O N Isrinkimo selection O N O N O N Lygiagretieji algoritmaiNaudojant daugiaprocesorinį kompiuterį ar paskirstyta kompiuteriu tinkla galima pasiekti ir dar geresniu rezultatu Geriausiu atveju pasiekiamas sudetingumas O log N