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 binomial 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 binomial fiind suficient, obtinandu-se astfel o complexitate de {$O(|V|*|E|*log |V|)$}

h2. Probleme de taietura in concursurile de algoritmica