Kodėl tiek DFS, tiek BFS O (V + E) laiko sudėtingumas

BFS algoritmas:

 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 

Taigi, manau, kad laiko sudėtingumas bus:

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

kur v yra nuo 1 iki n

Pirma, ar tai teisingai pasakiau? Antra, kaip yra O(N + E) ir intuicija, kodėl tai būtų tikrai malonu. Ačiū

84
13 июля '12 в 13:24 2012-07-13 13:24 paprastas yra nustatytas liepos 13 d. 12 val. 13:24 2012-07-13 13:24
@ 7 atsakymai

Jūsų suma

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

galima perrašyti kaip

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

ir pirmoji grupė yra O(N) , o kita yra O(E) .

193
13 июля '12 в 13:29 2012-07-13 13:29 atsakymą Mihai Maruseac pateikė liepos 12 d. 13:29 2012-07-13 13:29

DFS (analizė):

  • Viršutinės / briaunos etiketės nustatymas / įjungimas užima O(1) laiką
  • Kiekvienas viršūnė žymimas du kartus.
    • kartą kaip UNEXPLORED
    • kartą kaip VISIT
  • Kiekvienas kraštas pažymėtas du kartus.
    • kartą kaip UNEXPLORED
    • kartą kaip DISCOVERY arba BACK
  • Kiekvienam viršūnės taškui metodas vadinamas vieną kartą.
  • DFS veikia O(n + m) laiku, jei grafiką vaizduoja gretimų sąrašų struktūra
  • Prisiminkite, kad Σv deg(v) = 2m

BFS (analizė):

  • Viršutinės / briaunos etiketės nustatymas / priėmimas užima O (1) laiką
  • Kiekvienas viršūnė žymimas du kartus.
    • kartą kaip UNEXPLORED
    • kartą kaip VISIT
  • Kiekvienas kraštas pažymėtas du kartus.
    • kartą kaip UNEXPLORED
    • kartą kaip DISCOVERY arba CROSS
  • Kiekviena viršūnė įterpiama vieną kartą į eilę Li
  • Kiekvienam viršūnės taškui metodas vadinamas vieną kartą.
  • BFS veikia O(n + m) laiku, jei grafiką vaizduoja gretimų sąrašų struktūra
  • Prisiminkite, kad Σv deg(v) = 2m
34
13 июля '12 в 13:28 2012-07-13 13:28 Atsakymą pateikė TheNewOne liepos 13 d. 12 val. 2012-07-13 13:28

Labai supaprastintas be didelių formalumų: kiekvienas kraštas yra laikomas lygiai du kartus, o kiekvienas mazgas apdorojamas tiksliai vieną kartą, todėl sudėtingumas turi būti pastovus kraštų skaičiaus ir viršūnių skaičiaus.

14
17 дек. Atsakymą pateikia „ JavaFreak“ 17 d. 2014-12-17 09:04 '14 at 9:04 2014-12-17 09:04

Laiko sudėtingumas yra O(E+V) vietoj O(2E+V) , nes jei laiko sudėtingumas yra n ^ 2 + 2n + 7, tada jis yra parašytas kaip O (n ^ 2).

Todėl O (2E + V) yra parašyta kaip O (E + V)

nes skirtumas tarp n ^ 2 ir n yra reikšmingas, bet ne tarp n ir 2n.

7
10 сент. Atsakymą pateikė Dhruvam Gupta 10 rugsėjis. 2015-09-10 18:39 '15, 18:39, 2015-09-10 18:39

Manau, kad kiekvienas kraštas buvo vertinamas du kartus, ir kiekvienas mazgas buvo aplankytas vieną kartą, todėl bendras laiko sudėtingumas turėtų būti O (2E + V).

3
21 июля '15 в 11:23 2015-07-21 11:23 Kehe CAI atsakymas liepos 21 d. 15 d. 11:23 val. 2015-07-21 11:23

Trumpas, bet paprastas paaiškinimas:

Blogiausiu atveju reikės aplankyti visą viršų ir kraštą, taigi laiko sudėtingumas yra blogiausiu O (V + E)

1
27 июля '16 в 7:17 2016-07-27 07:17 atsakymą pateikė CodeYogi, liepos 27 d., 16 d., 07:17, 2016-07-27 07:17

Intuityvus paaiškinimas yra paprastas vieno ciklo analizė:

  • apsilankykite viršutiniame → o (1)
  • už kilpą visuose krintančiuose kraštuose → O (e), kur e yra briaunų, esančių ant nurodyto viršūnės v, skaičius.

Taigi bendras ciklo laikas yra O (1) + O (e). Dabar mes apibendriname kiekvieną viršūnę, kai kiekvienas viršūnė apsilankoma vieną kartą. Tai suteikia

Sigma_i

 <p> <span> O(1) + O(e) => <span> O(1) + <span> O(e) => O(V) + O(E) </p> 

[O (1) + O (e)]

0
07 авг. atsakymą pateikė Deepanker Mishra 07 rug . 2017-08-07 12:27 '17 12:27 pm 2017-08-07 12:27