[cly79902]

#programowanie #studia #studbaza

Jak wyznaczyć złożonośc algorytmu bąbelkowego?
bo mam zadanie w ktorej tresci jest podany program w pseudokodzie i mam wyznaczyc zlozonosc tego algorytmu.

Wiadomo ze zlozonosc babelkowego to o(n^2) ale jak to wyznaczyc

[borntobewild]

@cly79902: złożoność jednej pętli to n. Masz pętle w pętli wiec n*n

[cly79902]

@borntobewild: watpie by takie wytłumaczenie wystarczylo

[b.....a]

@cly79902: żeby przesunąć jeden element w najgorszym wypadku musisz wykonać n podmian elementów (zamiana jednego z drugim). Elementów jest n, więc będziesz miał w najgorszym wypadku n podmian dla n elementów.

[borntobewild]

@cly79902: o @bolinoga: ładnie Ci napisal :)

[cly79902]

@cly79902: @borntobewild: mam takie rozwiazanie

[b.....a]

@cly79902: @borntobewild: jak chcesz się przyjrzeć problemowi bliżej to podmian będzie mniej. Wydaje mi się, że w pierwszej pętli będziesz miał n-1 podmian. W każdej kolejnej możesz robić już tylko n-2, bo wiesz, że ostatni element już jest uporządkowany i na pewno nie będziesz miał wartości, którą za nią wepchniesz. Z każdą pętlą o jedną mniej iterację :)

Jeśli już coś takiego naskrobałeś to chociaż napisz skąd się bierze O(n^2)

[cly79902]

@bolinoga: zle sie czyta te ułamku tutaj, przepisze sobie na kartke i ogarne, dzieki

[cly79902]

@bolinoga: nie ogarniam, kiepsko ze nie da sie tu robic ułamkow