Junior
Ինչ է C++-ում std::vector դասի օպերացիաների ասիմպտոտիկ բարդությունը։
sobes.tech AI
Պատասխան AI-ից
std::vector հիմնական գործողությունների ասիմպտոտիկ բարդությունը՝
| Գործողություն | Միջին ժամանակ | Ամենավատ ժամանակ |
|---|---|---|
Էլեմենտին մուտք գործել ([], at) |
O(1) | O(1) |
| Ավելացնել/ջնջել վերջում | O(1) | O(N) |
| Ավելացնել/ջնջել սկզբում/միջինում | O(N) | O(N) |
չափը ստանալ (size) |
O(1) | O(1) |
չափը փոխել (resize) |
O(N) | O(N) |
Նշումներ:
- O(1) (հաստատ ժամանակ): Գործողությունը կատարվում է ֆիքսված քանակությամբ քայլերով, անկախ վեկտորի չափից:
- O(N) (գիծային ժամանակ): Գործողության կատարման ժամանակը ուղղակի proportional է վեկտորի տարրերի թվին (N):
Ավելին:
- Վերջում ավելացնելը/ջնջելը կարող է պահանջել O(N) ամենավատ դեպքում՝ հիշողության վերաօգտագործման (realloc) պատճառով, երբ ընթացիկ ծավալը բավարար չէ: Realloc-ի ժամանակ, ստեղծվում է նոր ավելի մեծ բուֆեր և բոլոր առկա տարրերը պատճենվում են դրան: Հիշողության բաշխման ռազմավարության շնորհիվ (հաճախ, ծավալը կրկնապատկել), միջին ժամանակը ավելացման/ջնջման համար վերջում՝ O(1):
- Միջինում, միջնամասում ավելացնելը/ջնջելը պահանջում է բոլոր հաջորդող տարրերի տեղափոխում, ինչը ժամանակ է պահանջում՝ O(N):
Օրինակ՝ push_back-ի ժամանակ վերաօգտագործման օրինակ:
// Ենթադրենք, վեկտորը ունի 4 ծավալ և լրացված է
std::vector<int> vec = {1, 2, 3, 4}; // Ծավալը = 4, չափը = 4
// Նոր տարր ավելացնելը պահանջում է վերաօգտագործում
vec.push_back(5); // Հնարավոր է, ծավալը դառնա 8, և բոլոր տարրերը պատճենվեն
// Այս դեպքում `push_back`-ը տևեց O(N) ժամանակ,
// որտեղ N՝ վերաօգտագործումից առաջ տարրերի քանակն է: