h2. Analiza complexitatii

In cadrul procedurii TaieturaMinima, vom apela procedura FazaTaieturiiMinime de $O(|V|)$ ori. Observam ca in cadrul acestei din urma proceduri, avem nevoie de o structura de date care sa poata efectua in mod eficient urmatoarele operatii: _extrage_cheia_maxima_ si _creste_valoarea_unei_chei_. Putem folosi un heap Fibonacci pentru a efecuta operatia _extrage_cheia_maxima_ in {$O(log V)$} amortizat, iar pentru _creste_valoarea_unei_chei_ in O(1) amortizat, obtinand astfel o complexitate finala de {$O(|V|*|E| + |V|^2^*log |V|)$}. Nu recomand insa implementarea unei asemenea structuri in conditii de concurs, un heap binar fiind suficient, obtinandu-se astfel o complexitate de {$O(|V|*|E|*log |V|)$}

In cadrul procedurii TaieturaMinima, vom apela procedura FazaTaieturiiMinime de $O(|V|)$ ori. Observam ca in cadrul acestei din urma proceduri, avem nevoie de o structura de date care sa poata efectua in mod eficient urmatoarele operatii: _extrage_cheia_maxima_ si _creste_valoarea_unei_chei_. Putem folosi un heap Fibonacci pentru a efecuta operatia _extrage_cheia_maxima_ in {$O(log |V|)$} amortizat, iar pentru _creste_valoarea_unei_chei_ in O(1) amortizat, obtinand astfel o complexitate finala de {$O(|V|*|E| + |V|^2^*log |V|)$}. Nu recomand insa implementarea unei asemenea structuri in conditii de concurs, un heap binar fiind suficient, obtinandu-se astfel o complexitate de {$O(|V|*|E|*log |V|)$}

h2. Probleme de taietura in concursurile de algoritmica