Ені бойынша іздеуді талдау

$V$‍ шыңдар жиынтығы және $E$‍ жиектер жиынтығы бар график үшін ені бойынша іздеу қанша уақытты алады? Жауап - $O(V+E)$‍ уақыт.

$O(V+E)$‍уақыты нені білдіретінін көрейік. Қазіргі уақытта $|E|\ge |V|$‍ деп есептейік, бұл көптеген графиктерге қатысты, әсіресе біз ені бойынша іздейміз. Содан кейін $|V|+|E|\le |E|+|E|=2\cdot |e|$‍. Біз асимптотикалық белгілеудегі тұрақты факторларды елемейтіндіктен, $|E|\ge |V|$‍, $O(V+E)$‍ шынымен $O(E)$‍дегенді білдіреді. Алайда, егер бізде $|E|<|V|$‍ болса, онда $|V|+|E/\le /V/+/V/=2\cdot |V/$‍, сондықтан $O(V+E)$‍ шынымен $O(V)$‍дегенді білдіреді. $O(V+E)$‍ шынымен $O(max(V,E))$‍дегенді білдіретін екі жағдайды да біріктіре аламыз. Жалпы, егер бізде $x$‍ және $y$‍ параметрлері болса, онда $O(x+y)$‍ шынымен $O(max(x,y))$‍дегенді білдіреді.

(Ескерту, егер әр шыңнан басқа шыңдарға апаратын жол болса, графқа байланысты екенін ескеріңіз. Графикте болуы мүмкін және әлі де қосыла алатын жиектердің ең аз саны - $|V|-1$‍. $|E|=|V|-1$‍ болатын График еркін ағаш деп аталады.)

Ені бойынша іздеу $O(V+E)$‍ уақыт аралығында қалай жасалады? Қашықтықты және ісшарасын (предшественникті) инициализациялау үшін әр шыңға $O(V)$‍ уақыт қажет (іс жүзінде $\mathrm{\Theta }(V)$‍ уақыт). Әр шыңға бір реттен көп емес барады, өйткені бірінші рет жеткенде ғана оның қашықтығы нөлге тең болады, сондықтан әр шың кезекке бір реттен артық қойылмайды. Біз шыңға құлаған жиектерді тек біз кірген кезде зерттейтіндіктен, әр шеті екі реттен көп емес, әр шыңы үшін бір рет зерттеледі. Осылайша, ені бойынша іздеу ең алдымен шыңдарға бару үшін $O(V+E)$‍ жұмсайды.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.