რისი არის სიაში ელემენტებთან ოპერაციების ასიმპტოტიკური სირთულე?

ეს დამოკიდებულია სიას ტიპსა და ოპერაციაზე.

საშუალოდ განიხილავენ შემდეგი ტიპების სიებს:

• ერთკავშირიანი სია
• ორკავშირიანი სია
• მასივი (როგორც სიის კერძო შემთხვევა)

ოპერაციები:

• ინდექსით წვდომა
• ჩასმა
• წაშლა
• მნიშვნელობის ძიება

ოპერაცია	ერთკავშირიანი სია	ორკავშირიანი სია	მასივი
ინდექსით წვდომა	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) (ლინეურული დრო): ოპერაციის შესრულების დრო პროპორციულია სიის ზომასთან. მაგალითად, ელემენტის ძიება არასწორ სიისთვის.
• O(log n) (ლოგარითმული დრო): ოპერაციის შესრულების დრო იზრდება ლოგარითმულად სიის ზომის ზრდასთან. ხშირად გამოიყენება სორტირებულ მონაცემებთან მუშაობისას (მაგალითად, ბინარული ძიება).

დეტალები:

• ერთკავშირიან სიაში: ჩასმა დასაწყისში - O(1). ჩასმა ბოლოს ან ინდექსით - საჭირო ხდება სიის გავლა, რაც იძლევა O(n).
• ორკავშირიან სიაში: ჩასმა დასაწყისსა და ბოლოში - O(1). ჩასმა/წაშლა ელემენტის მისამართზე - O(1), მაგრამ ამ ელემენტის ძიება მნიშვნელობით ან ინდექსით - O(n).
• მასივში: ინდექსით წვდომა - O(1). ჩასმა ან წაშლა შუა ნაწილში საჭიროებს ელემენტების გადანაცვლებას, რაც იძლევა O(n). ჩასმა/წაშლა ბოლოში, თუ მოცულობა საკმარისია (მაგალითად, std::vector-ში გარკვეული მოცულობით), შეიძლება იყოს O(1) საშუალოდ, მაგრამ უარეს შემთხვევაში (რეკლამაცია) - O(n).