Junior
Milline on nimekirja elementidega toimingute asümptootne keerukus?
sobes.tech AI
Vastus AI-lt
Sõltub loendi tüübist ja operatsioonist.
Tavaliselt käsitletakse järgmisi loenditüüpe:
- Üksikühendusega loend
- Kaheühendusega loend
- Massiiv (kui loendi erijuht)
Operatsioonid:
- Juurdepääs indeksi järgi
- Lisamine
- Kustutamine
- Väärtuse otsimine
| Operatsioon | Üksikühendusega loend | Kaheühendusega loend | Massiiv |
|---|---|---|---|
| Juurdepääs indeksiga | O(n) | O(n) | O(1) |
| Lisamine | O(1) (alguses) | O(1) (alguses/lõpus) | O(n) |
| Kustutamine | O(n) | O(n) | O(n) |
| Väärtuse otsimine | O(n) | O(n) | O(n) |
Selgitused:
- O(1) (konstantne aeg): operatsioon kestab fikseeritud aja, sõltumata loendi suurusest. Näiteks elemendi juurdepääs indeksiga massiivis.
- O(n) (jooneline aeg): operatsiooni täitmise aeg on proportsionaalne loendi suurusega. Näiteks otsing mittesorted loendis.
- O(log n) (logaritmiline aeg): operatsiooni täitmise aeg kasvab logaritmiliselt loendi suuruse kasvuga. Kasutatakse sageli sorteeritud andmetega töötamisel (näiteks binaarotsing).
Detailid:
- Üksikühendusega loendis: Lisamine alguses - O(1). Lisamine lõpus või indeksi järgi nõuab läbikäiku loendis kuni vajaliku elemendini, mis annab O(n).
- Kaheühendusega loendis: Lisamine alguses ja lõpus - O(1). Lisamine/kustutamine sõlme aadressil - O(1), kuid selle sõlme otsimine väärtuse või indeksi järgi - O(n).
- Massiivis: Juurdepääs indeksiga - O(1). Lisamine või kustutamine keskel nõuab elementide nihutamist, mis annab O(n). Lisamine/kustutamine lõpus, kui on piisavalt vaba ruumi (näiteks
std::vectorteatud mahuga), võib olla keskmiselt O(1), kuid halvimates tingimustes (reallocatsioon) - O(n).