Time and Space Complexity
Coddy'nin Prim Algoritması - Çizge Algoritmaları kursunda ders 7 / 9.
Zaman Karmaşıklığı:
- Buradaki kenar tarama (edge-scan) versiyonu O(V * E)'dir: V-1 tur, her biri tüm E kenarlarını tarar. İkili yığın (binary heap) ve komşuluk listeleri ile Prim, O((V + E) log V) süresinde çalışır.
Alan Karmaşıklığı:
inTreedizisi için O(V) (artı girdi kenarları).
Özet:
- Prim, her köşe dahil edilene kadar, her zaman ağaçtan ayrılan en ucuz kenarı ekleyerek tek bir ağaç büyütür.
- Farklı bir strateji kullanarak Kruskal ile aynı minimum toplam ağırlığı üretir.
Kendin dene
Bu ders bir kod alıştırması içermiyor.
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Prim Algoritması - Çizge Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity