Kompleksitas Waktu dan Ruang
Pelajaran 7 dari 9 dalam kursus Algoritma Kruskal: Algoritma Graf di Coddy.
Kompleksitas Waktu:
- Mengurutkan E edge membutuhkan O(E log E); setiap operasi union-find hampir O(1) dengan kompresi jalur, sehingga Kruskal klasik membutuhkan O(E log E). Versi pemilihan minimum yang kita buat di sini membutuhkan O(E2), yang cukup baik untuk graf kecil.
Kompleksitas Ruang:
- O(V) untuk array parent (ditambah edge input).
Ringkasan:
- Kruskal membangun MST dengan menambahkan edge tanpa siklus yang paling murah di setiap langkah, menggunakan union-find untuk memeriksa siklus.
- Semua MST memiliki bobot total yang sama, jadi jawabannya unik.
Coba sendiri
Pelajaran ini tidak memiliki tantangan kode.
Uji dirimuPelajaran ini berisi kuis singkat. Mulai pelajarannya untuk menjawab kuis dan melacak progresmu.
Semua pelajaran di Algoritma Kruskal: Algoritma Graf
2Algoritma
Bagaimana cara kerjanya?Kode SemuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online