Junior
Ի՞նչ է ցուցակի տարրերով գործողությունների ասիմպտոտիկ բարդությունը։
sobes.tech AI
Պատասխան AI-ից
Արժեքը կախված է ցանկի տեսակից և գործողությունից:
Ընդհանուր առմամբ, դիտարկվում են հետևյալ տեսակի ցանկեր.
- Միակողմանի կապակցված ցանկ
- Երկկողմանի կապակցված ցանկ
- Մասիվ (որպես ցանկի հատուկ դեպք)
Գործողություններ:
- Հասանելիություն ըստ ինդեքսի
- Ավելացում
- Ջնջում
- Արժեքի որոնում
| Գործողություն | Միակողմանի կապակցված ցանկ | Երկկողմանի կապակցված ցանկ | Մասիվ |
|---|---|---|---|
| Հասանելիություն ըստ ինդեքսի | O(n) | O(n) | O(1) |
| Ավելացում | O(1) (սկիզբում) | O(1) (սկիզբ/ավարտ) | O(n) |
| Ջնջում | O(n) | O(n) | O(n) |
| Արժեքի որոնում | O(n) | O(n) | O(n) |
Նշումներ:
- O(1) (Կոնստանտ ժամանակ): Գործողությունը կատարվում է ֆիքսված ժամանակ, անկախ ցանկի չափից: Օրինակ, ինդեքսով մուտք գործել զանգվածում:
- O(n) (Գծային ժամանակ): Գործողության կատարման ժամանակը proportional է ցանկի չափին: Օրինակ, որոնում անտարբեր ցանկում:
- O(log n) (Լոգարիթմական ժամանակ): Գործողության կատարման ժամանակը logaritմիկորեն աճում է ցանկի չափով: Հաճախ հանդիպում է դասավորված տվյալների հետ աշխատելիս:
Մանրամասներ:
- Միակողմանի կապակցված ցանկում՝
- Մուտքագրում սկզբում - O(1):
- Մուտքագրում վերջում կամ ըստ ինդեքսի - անհրաժեշտ է անցնել ցանկը մինչև ցանկալի տարր, ինչը տալիս է O(n):
- Երկկողմանի կապակցված ցանկում՝
- Մուտքագրում սկզբում և վերջում - O(1):
- Մուտքագրում/ջնջում որոշակի դիրքում - O(1), բայց որոնում այդ հանգույցը արժեքով կամ ինդեքսով - O(n):
- Մասիվում՝
- Հասանելիություն ըստ ինդեքսի - O(1):
- Միջինում, մուտքագրում կամ ջնջում միջին մասում պահանջում է տարրերի տեղափոխում, ինչը տալիս է O(n):
- Մուտքագրում/ջնջում վերջում, եթե կա պահեստային հզորություն (օրինակ,
std::vector-ում որոշակի հզորությամբ), կարող է լինել միջինում O(1), բայց ամենավատ դեպքում (reallocation) - O(n):