@legolass znaczy tak, będzie liniowe, tylko jak do tego dojść. W sensie będzie np. O(2N+5) co daje nam finalnie O(N). Potrzebuję wzór z którego dojdę do O(N)
@Deltamir: W pierwszej pętli każdy obrót pętli powoduje zwiększenie co najmniej jednej zmiennej i lub j. Czyli w negatywnym przypadku wykonamy maksymalnie (N + M - 1) obrotów i wtedy na pewno któraś warunek wyjścia zostanie spełniony.
W drugiej pętli w najgorszym przypadku zmienna q na początku = 1 i też w każdym obrocie jest inkrementowana. W związku z tym w tym pesymistycznym przypadku będzie N obrotów pętli.
@Deltamir: Po prostu jeśli po wyjściu z pierwszej pętli zmienna i będzie wynosiła C to druga pętla wykona się N - C razy. czyli pierwsza wykona się C + M - 1 to druga N - C razy (C<=N), czyli w sumie C + M -1 + N - C = N + M -1 = Θ(N +M)
Dymy kończą się tam, gdzie komuś może stać się realna krzywda. To co zrobił Tyburski były bardzo niebezpieczne i jako koneserowi patologi jest mi smutno. Należy to potępić.
Hej Mirki. Pomoże ktoś obliczyć złożoność O( o duże)?
Z może być dowolną naturalną liczbą. Dajmy na to 5. Obie tablice są posortowane niemalejąco.
W drugiej pętli w najgorszym przypadku zmienna q na początku = 1 i też w każdym obrocie jest inkrementowana. W związku z tym w tym pesymistycznym przypadku będzie N obrotów pętli.
Czyli najgorszy przypadek
O(n!)
i pora na CS-a@ponton: lepiej? ( ͡° ͜ʖ ͡°)