Mengapa kompleksitas waktu dari DFS dan BFS O (V + E)

132

Algoritma dasar untuk BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

Jadi saya akan berpikir kompleksitas waktu adalah: 

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

dimana vvertex 1untukn

Pertama, apakah yang saya katakan benar? Kedua, bagaimana ini O(N + E), dan intuisi mengapa akan sangat bagus. Terima kasih

algorithm time-complexity graph-theory breadth-first-search biasa
sumber

Jawaban:

268

Jumlah anda

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

dapat ditulis ulang sebagai

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

dan kelompok pertama adalah O(N)sementara yang lain adalah O(E).

Mihai Maruseac
sumber
1
Tetapi setiap simpul harus diekstraksi dari antrian, dan ini adalah log (| Q |) Bagaimana dengan bagian ini?
Yola
3
log (| Q |) <log (N) <N maka Anda dapat dengan aman mengabaikan istilah dalam asimptotik
Mihai Maruseac
2
Jika dalam daftar adjacency, setiap simpul terhubung ke semua simpul lainnya, apakah kompleksitasnya akan setara dengan O (V + E) = O (V + V ^ 2) = O (V ^ 2). E = V ^ 2 karena paling banyak edge = V ^ 2.
Maks
Menurut jawaban Anda, bukankah kompleksitasnya menjadi O (V + 2E)? Karena setiap sisi mungkin memiliki sisi yang sama dengan sisi lainnya?
karansky
2
Istilah konstan dapat dihapus.
Mihai Maruseac
41

DFS (analisis):

  • Mengatur / mendapatkan label titik / tepi membutuhkan O(1)waktu
  • Setiap simpul diberi label dua kali
    • sekali tidak dieksplorasi
    • sekali DIKUNJUNGI
  • Setiap sisi diberi label dua kali
    • sekali tidak dieksplorasi
    • sekali sebagai PENEMUAN atau KEMBALI
  • Metode incidentEdges dipanggil satu kali untuk setiap titik
  • DFS berjalan dalam O(n + m)waktu asalkan grafik diwakili oleh struktur daftar adjacency
  • Ingat itu Σv deg(v) = 2m

BFS (analisis):

  • Mengatur / mendapatkan label titik / tepi membutuhkan O (1) waktu
  • Setiap simpul diberi label dua kali
    • sekali tidak dieksplorasi
    • sekali DIKUNJUNGI
  • Setiap sisi diberi label dua kali
    • sekali tidak dieksplorasi
    • sekali sebagai DISCOVERY atau CROSS
  • Setiap dhuwur disisipkan satu kali ke dalam suatu urutan Li
  • Metode incidentEdges dipanggil satu kali untuk setiap titik
  • BFS berjalan dalam O(n + m)waktu asalkan grafik diwakili oleh struktur daftar adjacency
  • Ingat itu Σv deg(v) = 2m
Yang baru
sumber
tnx untuk edit saya baru di sini jadi saya masih mencoba mengelola dengan layar edit :)
TheNewOne
1
terima kasih untuk lebih spesifik dengan menyebutkan bahwa grafik harus diwakili oleh struktur daftar adjacency, itu menggangguku mengapa DFS adalah O (n + m), saya akan berpikir itu O (n + 2m) karena setiap sisi dilintasi dua kali dengan mundur.
mib1413456
22

Sangat disederhanakan tanpa banyak formalitas: setiap tepi dianggap tepat dua kali, dan setiap simpul diproses tepat satu kali, sehingga kerumitan harus merupakan kelipatan konstan dari jumlah tepi serta jumlah simpul.

Neetesh Dadwariya
sumber
Jauh lebih mudah dipahami daripada notasi matematika tanpa penjelasan lebih lanjut meskipun itulah gunanya Google.
mLstudent33
11

Kompleksitas waktu O(E+V)alih-alih O(2E+V)karena jika kompleksitas waktu adalah n ^ 2 + 2n + 7 maka ditulis sebagai O (n ^ 2).

Karenanya, O (2E + V) ditulis sebagai O (E + V)

karena perbedaan antara n ^ 2 dan n penting tetapi tidak antara n dan 2n.

Dhruvam Gupta
sumber
@Am_I_Membantu seseorang meminta 2E di atas dalam notasi besar-oh .... itu sebabnya 2 tidak dianggap dalam kompleksitas waktu.
Dhruvam Gupta
@Am_I_Helpful lihat saja posting di atas jawaban saya .... di sana pengguna bernama Kehe CAI telah menulis "Saya pikir setiap sisi telah dianggap dua kali dan setiap node telah dikunjungi sekali, sehingga total kompleksitas waktu harus O (2E + V ). " Jadi saya menjawab dengan jelas .... Mengerti !!!
Dhruvam Gupta
Saya menghapus downvote saya hanya karena Anda mengedit jawaban Anda,
Am_I_Helpful
3

Saya pikir setiap edge telah dipertimbangkan dua kali dan setiap node telah dikunjungi sekali, jadi total kompleksitas waktu harus O (2E + V).

Kehe CAI
sumber
Bahkan saya merasakan hal yang sama. Adakah yang bisa memberikan penjelasan lebih lanjut tentang ini?
Chaitanya
12
Analisis Big O mengabaikan konstanta. O (2E + V) adalah O (E + V).
Hemm
3

Penjelasan intuitif untuk ini adalah dengan hanya menganalisis satu loop:

  1. kunjungi titik -> O (1)
  2. a untuk loop pada semua tepi insiden -> O (e) di mana e adalah sejumlah insiden tepi pada verteks yang diberikan v.

Jadi total waktu untuk satu loop adalah O (1) + O (e). Sekarang jumlahkan itu untuk setiap simpul karena setiap simpul dikunjungi sekali. Ini memberi

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)
Ultrablendz
sumber
2

Penjelasan singkat tapi sederhana:

Saya yang terburuk Anda harus mengunjungi semua titik dan tepi maka kompleksitas waktu dalam kasus terburuk adalah O (V + E)

CodeYogi
sumber