[Deltamir]

#programowanie #informatyka

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.

[legolass]

@Deltamir: Moim zdaniem O(MAX(N,M)). Można też zapisać jako O(N+M), ale to będzie to samo

[Deltamir]

@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)

[legolass]

@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.

Czyli najgorszy przypadek

[Deltamir]

@legolass Ale jesteś super. Dzięki wielkie (ʘ‿ʘ)

[legolass]

@Deltamir: Można łatwo udowodnić, że maksymalna liczba obrotów to (N + M -1) ale to nie wypływa na O().

[Deltamir]

@legolass Gdybyś to rozwinął to byłbym bardzo wdzięczny.

[ponton]

@Deltamir: O(n!) i pora na CS-a

[legolass]

@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)

@ponton: lepiej? ( ͡° ͜ʖ ͡°)