|
Samaradorligi va cheklashlar
|
| bet | 3/4 | | Sana | 16.02.2024 | | Hajmi | 261,72 Kb. | | #157914 |
Bog'liq Ma\'ruza 5. SteklarSamaradorligi va cheklashlar
Samaradorligi:
Aytaylik n - stekdagi elementlar soni bo'lsin. Ushbu o'lchamdagi stek amallari uchun xotira va vaqt bahosi quyidagicha:
Xotira sarfi(n ta kiritish amali uchun) − O(n);
Stekkar element qo’shish Push() amali uchun vaqt sarfi − O(1);
Stekda elementni olib tashlash Pop() amali uchun vaqt sarfi − O(1);
Peek() orqali elementni olish uchun vaqt sarfi − O(1);
IsEmpty() uchun vaqt sarfi − O(1);
Stekdagi elementlar ro‘yxatini olish Print() amali uchun vaqt sarfi − O(n).
Cheklovlar:
Boshidanoq stek elementlarini saqlash uchun ishlatiladigan statik massivining maksimal hajmini aniqlash kerak va uni o‘zgartirib bo‘lmaydi. Yangi elementni to'liq stekga qo’shishga urinish amalga oshirishga bog'liq istisnoni keltirib chiqaradi.
Dinamik massivga asoslangan amalga oshirish.
Stekni amalga oshirishning ushbu usulida stek elementlarini saqlash uchun dinamik massivga xotiradan ko’rsatilgan o’lchamda dinamik ravishda joy ajratiladi. Agar stek to'la bo'lsa, unda yangi elementni kiritishda stek hajmini oshirish kerak bo'ladi, bu ikki usulda amalga oshirilishi mumkin.
Birinchi usul (inkrement usul): har safar yangi element kiritilganda massiv hajmini 1 taga oshirish. Bu usul juda qimmatga tushadi.
Misol uchun, n = 1 xolat uchun stekka yangi elementni qo’shish uchun o’lchami 2 bo’lgan yangi massiv yaratiladi va stekni eski massivdagi barcha elementlari yangi massivga ko'chiriladi va yangi element oxirida qo'shiladi. n = 2 bo’lgan xolatda yangi elementni qo’shish uchun 3 o'lchamdagi yangi massiv yaratiladi va eski massivning barcha elementlarini yangi massivga nusxalash, yangi elementni oxiriga qo'shish va hokazo. Xuddi shu tarzda, n = n - 1 uchun, agar yangi element kiritilsa, yangi n o'lchamli massiv yaratiladi va eski massivning barcha elementlari yangi massivga ko'chiriladi va yangi element oxirida qo'shiladi. n ta kiritish amallaridan keyin umumiy vaqt samaradorligi T(n) (nusxalash amallari soni) 1 + 2 + ... + n ≈ O(n2) ga proportsionaldir.
Ikkinchi yo'l: (takroriy ikkilantirish).
Massivni ikki barobarga oshirish texnikasidan foydalanib, bahoni (vaqt samaradorligini) yaxshilash mumkin. Agar massiv to'la bo'lsa, ikki barobar kattaroq yangi massiv yaratiladi va elementlar unga ko'chiriladi. Ushbu yondashuv bilan n ta elementni ko'chirish n ga proportsional vaqtni oladi (n2 emas).
Misol uchun, biz dastlab n = 1 dan boshlab, n = 32 gacha o'tdik deb faraz qilaylik. Bu shuni anglatadiki, biz 1,2,4,8,16 ga ikkilantiramiz.
Xuddi shu yondashuvni tahlil qilishning yana bir usuli: n = 1 xolatda, agar element qo'shmoqchi bo'lsak, biz massivning joriy hajmini ikki barobarga oshirishimiz va eski massivning barcha elementlarini yangi massivga nusxalashimiz kerak.
n = 1 xolatda biz 1 nusxa ko'chirish amalini bajaramiz, n = 2 xolatda 2 nusxa ko'chirish amalini va n = 4 xolatda 4 nusxa ko'chirish amalini bajaramiz va hokazo. n = 32 ga yetganda, nusxa ko'chirish amallarining umumiy soni 1 + 2 + 4 + 8 + 16 = 31 bo'ladi, bu taxminan 2n qiymatiga teng (32). Endi muhokamani umumlashtiramiz. n ta element qo’shish amali uchun massiv o’lchami logn marta ikkilantirildi. n ta qo'shish amallari uchun umumiy vaqt sarfi T(n) quyidagiga teng bo’ladi:
Ya’ni T(n) - O(n) ga teng.
Quyida stek BATni dinamik massiv orqali amalga oshirish misoli keltirilgan:
using System;
using System.Collections.Generic;
using System.Text;
namespace DinArrayStack
{
public class DArrStack
{
private T[] items;
private int count;
const int n = 1;
public DArrStack(int length = n)
{
items = new T[length];
}
public bool IsEmpty
{
get { return count == 0; }
}
public int Count
{
get { return count; }
}
public void Push(T item)
{
// stek o’lchamini ikkilantiramiz
if (count == items.Length)
Resize(items.Length * 2);
items[count++] = item;
}
public T Pop()
{
// Stek bo’sh bo’lsa istisno xolatini yuzaga keltirish
if (IsEmpty)
throw new InvalidOperationException("Stek bo’sh");
T item = items[--count];
items[count] = default(T); //havolani qayta o'rnating
return item;
}
public T Peek()
{
return items[count - 1];
}
private void Resize(int max)
{
T[] tempItems = new T[max];
for (int i = 0; i < count; i++)
tempItems[i] = items[i];
items = tempItems;
}
public void Print()
{
for(int i=0;i{
Console.WriteLine(items[i]);
}
}
}
Dinamik massiv asosidagi stekdan foydalanishga misol:
using System;
namespace DinArrayStack
{
class Program
{
static void Main(string[] args)
{
try
{
DArrStack stack = new DArrStack();
// stekka 4 ta element qo’shish
stack.Push("Anvar");
stack.Push("Rustam");
stack.Push("Diana");
stack.Push("Sattor");
Console.WriteLine("Stekdagi elementlar soni:{0}", stack.Count);
Console.WriteLine("Stekdagi elementlar ro’yxati");
stack.Print();
Console.WriteLine("Stekdan element olish");
// 1 ta element olish
var head = stack.Pop();
Console.WriteLine(head); // Sattor
head = stack.Pop();
Console.WriteLine(head);
head = stack.Pop();
Console.WriteLine(head);
// stek oxiridan elementni o’chirib tashlamasdan olish
head = stack.Peek();
Console.WriteLine(head); // Diana
Console.WriteLine("Stekdagi elementlar soni");
stack.Print();
}
catch (InvalidOperationException ex)
{
Console.WriteLine(ex.Message);
}
Console.ReadKey();
}
}
}
|
| |
