11-маъруза Йўналтирил маган графлар

Primo algoritmi samaradorligi

• Samaradorlik grafni tashkil etish va minimal narxli daraxtga tegishli bo’lmagan tugunlarni saqlash usuliga bog’liq.
• Agar Q navbat massiv ko’rinishida tashkil etilsa, Extract.Min(Q) amali O(n) ga bog’liq va minimal vaznli yoylarni daraxtga o’zlashtirishga O(1) ta amal sarflanadi.
• Agar Q navbat binar piramida ko’rinishida tashkil etilsa, u xolda Extract.Min(Q) amali O(log(n)) gacha kamayadi.ammo minimal vaznli yoylarni daraxtga o’zlashtirish amali miqdori O(log(n)) ga oshadi.