Hej mam takie zadanko do zrobienia:
"Zaprojektuj algorytm wykonujący łączenie dwóch ciągów niemalejących w jeden ciąg uporządkowany niemalejąco.
Nie korzystaj z sortowania. Do rozwiązania dodaj analizę pesymistycznej złożoności swojego algorytmu, uzasadnij że algorytm się zakończy."
kod który napisałem wygląda w ten sposób:
https://pastebin.com/Q2aiTtEW
tylko nie wiem jak zabrać się za analizę złożoności i czy dobrze do tego podchodzę, czy mogę przyjąć, że w najbardziej pesymistycznym przypadku 2 ciągi będą jednakowej długości, oraz funkcja odpowiedzialna za przesuwanie indeksu będzie za każdym razem przechodzić przez całą długość ciągu, a więc złożoność będzie rzędu n^3, gdzie n-długość ciągu ?
0
1
Przy zlozonosci pamieciowej O(n+m) optymalnie byloby przeliczyc to ze zlozonoscia obliczeniowa O(n+m).
Przy zlozonosci pamieciowej O(1) tez sie da zrobic O(n+m), ale nie papietam czy w kazdym wypadku.
0
vpiotr napisał(a):
Przy zlozonosci pamieciowej O(n+m) optymalnie byloby przeliczyc to ze zlozonoscia obliczeniowa O(n+m).
Przy zlozonosci pamieciowej O(1) tez sie da zrobic O(n+m), ale nie papietam czy w kazdym wypadku.
Chodzi mi o oszacowanie złożoności obliczeniowej, i czy w dobry sposób rozumuję. Możesz napisać skąd to O(n+m)? (tak jak pisałem według mojego rozumowania wychodzi O(n^3) )
1
Masz dwa ciagi, jesli sa roznej dlugosci (a lepiej tak rozpatrywac) to masz dwie dlugosci: n i m.
0
vpiotr napisał(a):
Masz dwa ciagi, jesli sa roznej dlugosci (a lepiej tak rozpatrywac) to masz dwie dlugosci:
nim.
Ale czy bardziej pesymistyczna nie będzie wersja gdy są tej samej długości? Poza tym, mam tam 2 pętle zagnieżdżone, to jeśli rozpatrujemy różną długość, to nie będzie n*m, a nie n+m ?
0
vpiotr napisał(a):
https://www.geeksforgeeks.org/efficiently-merging-two-sorted-arrays-with-o1-extra-space/
No tu jest to inaczej zrobione nie wiem jak mam to do swojego algorytmu odnieść, mógł by ktoś wytłumaczyć jak tą złożoność oszacować na podstawie konkretnie mojego algorytmu ?
1
Masz zwykły bąbelkowy bubel, czyli O(N^2)
0
_13th_Dragon napisał(a):
Masz zwykły bąbelkowy bubel, czyli
O(N^2)
Bubel czy nie bubel, nie istotne, jedynym moim zadaniem jest poprawnie oszacować złożoność. dlaczego O(N^2) a nie O(N^3) ?