|
IsEmpty()
\(O(1)\)
Size()
|
| bet | 5/6 | | Sana | 15.05.2024 | | Hajmi | 199,62 Kb. | | #234109 |
Bog'liq Qo\'ziboyev Jamshid Algoritmlarni LoyihalashIsEmpty()
|
\(O(1)\)
|
Size()
|
\(O(1)\)
|
Barcha amallarni asosini o’zlashtirish amali tashkil qilgani sababi barcha metodlar \(O(1)\) vaqtda bajariladi.
Massivga asoslangan Stek. Massivning qulayliklaridan biri bu indeks orqali massivda joylashgan elementni vaqtda qaytara olishdir. Lekin massivdagi elementlar soni ko’payib ketsa qimmatbaho amal – hajmni kengaytirish lozim bo’ladi. O’z hajmini o’zi o’zgartira oladigan massiv dinamik massiv deyiladi.
Amal
|
Murakkablik
|
Push(T value)
|
Resize()ga qarang.
|
Pop()
|
\(O(1)\)
|
Peek()
|
\(O(1)\)
|
IsEmpty()
|
\(O(1)\)
|
Size()
|
\(O(1)\)
|
Resize()
|
Eng yomon holatda \(O(n)\), o’rtacha esa \(O(1)\) vaqt oladi.
|
Nazariyaga ko’ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize()ning chaqirilish ehtimolligi har chaqirilgandan so’ng pasayib boradi. Natijada, yuqoridagi metodni vaqt murakkablikka ega deb qabul qilishimiz mumkin.
"Merge" sort
[L,R] oraliq m=(L+R)/2 oʻrtasi orqali ikkita [L,M] va [m+1,R] oraliqda ajratiladi va ular alohida saralanadi.Keyin bu saralangan oraliqlar birlashtirilib, berilgan [L,R] oraliqda qoʻyib ketiladi.
Merge sort ning to’liq kodi
|
| |
