[Deltamir]

#informatyka #programowanie

Hej. Chciałbym się tylko upewnić w kwestii najgorszego przypadku, a mianowicie czy będzie to O(N+N-1)+1 czy O(N+N-1) dla schematu blokowego z załącznika. Przyjmujemy, że N i M są równe. Pętla A(i)<B(j) zmierza dalej w najgorszym przypadku dla N+N-1 i tu pytanie czy dodaję to jedno wykonanie i<=N (dla najgorszego przypadku będzie to N<=N), a w następnym obrocie N+1<=N co da nam już sprzeczność) czy jest to wykonywane w ramach tego N+N-1 wykonania?

[moon_bluebird]

@Deltamir: łooo panie

[tomek_27]

@Deltamir w technikum nienawidziłem tego tfu na to, jeszcze musieliśmy na kartkach to rozpisywać

[kafapre]

@Deltamir: nie miałem wyznaczania złożoności na podstawie algorytmu blokowego ale widzę to tak: w najgorszym przypadku algorytm przejdzie pierwsza pętlę M razy (tylko przypadek z inkrementacją j), a drugą N razy (inkrementacja i). Czyli złożoność bedzie liniowa: O(N+M).

[Deltamir]

@kafapre czyli by wychodziło w mojej wersji na (N+N-1) + 1 = 2N. W mojej wersji N jest równe M, bo mam zrobić funkcje od jednej zmiennej, więc je zrównałem. Więc wychodzi ostatecznie na 2N.

[kafapre]

@Deltamir: no, tylko skąd wzięło Ci się -1 i +1?

[Deltamir]

@kafapre Najgorszy przypadek dla A(i) < B(j) to N+M - 1. Dobrze to widać gdy A=[2, 4,6], B=[1, 3,5] Wtedy pętla się kończy po pięciu obrotach (3+3-1) ze zmiennymi j=4, i=3 i dochodzi do warunku i<=N (3<=3) i tu pytanie czy ten jeden obrót wyliczyć czy jest on w ramach ruchu (N+M-1)

[asciiterror]

@Deltamir: hmm, ale O(N+N-1)+1 i O(N+N-1) to raczej dokładnie to samo co O(N), zresztą nie spotkałem się z czymś takim jak O(...)+x

[Deltamir]

@asciiterror znaczy to wszystko jest pod O (N+N-1+1). Chodzi mi tylko jak w tym przypadku będzie czy O(N+N-1) czy O(N+N-1+1)

[asciiterror]

@Deltamir: O(N+N-1+1) = O(2N) = O(N) = O(N+N-1)
nie do końca rozumiem o co pytasz, chodzi o ilość porównań czy dodawań?

[Deltamir]

@asciiterror wiem co się dalej robi. Chcę mieć dobrą funkcje, którą będę mógł sprowadzić ostatecznie do O(N). Jeśli F(N) = O(N+N-1+1) jest poprawne dla tego algorytmu to już wiem wszystko. Zastanawiałem się po prostu czy tu będzie na starcie O(N+N-1+1) czy O(N+N-1) ( ͡º ͜ʖ͡º)

[asciiterror]

@Deltamir: to jak chcesz konkretną funkcję to może porzuć na razie tą całą "notację dużego O" i policz dokładnie ile jest tych porównań czy dodawań. Tak jak robisz to bez sensu się zastanawiać bo O(N+N-1+1) i O(N+N-1) to jest absolutnie dokładnie to samo, ale N+N i N+N-1 to nie to samo

[Deltamir]

@asciiterror ok, trochę to wprowadza w błąd ale wracając do pytania. Czy funkcja F(N) = (N+N-1)+1 będzie odpowiednia do wyznaczenia dużego O?

Funkcja dochodzi do i<=N w stanie (N+N-1) - nie ma gorszej możliwości i cały czas się zastanawiam czy pojedyncze wykonanie i<=N (Będzie to w tym przypadku N<=N) jest wykonywane w ramach ruchu N+N-1 czy to jest coś nowego i będzie finalnie N+N-1+1?

[asciiterror]

@Deltamir: tak, dlaczego nie? w dużym O chodzi tylko o część funkcji która najszybciej rośnie wraz ze zwiększeniem argumentu, z pominięciem stałych. Tzn. dla F(N) = (N+N-1)+1 (=2N) to będzie O(F) = N, bo pomijasz zupełnie to 2 i wszystko co rośnie wolniej niż N (+1-1 w ogóle nie rośnie więc pomijasz). Pytanie tylko czy funkcja jest dobra :)

[Deltamir]

@asciiterror Dokładnie i cały czas staram się upewnić czy ta funkcja jest odpowiednia do tego algorytmu :)

[Deltamir]

@asciiterror Wszystko co muszę wiedzieć to czy to wykonuje się w ramach ruchu N+N-1 czy jest to coś nowego i będzie N+N-1+1 :)

Przypominam, ten warunek w tym przypadku zadziała tylko raz ( ͡º ͜ʖ͡º)

[asciiterror]

@Deltamir: w dużym O nie liczysz ruchów, tylko operacje - w tym przypadku dodawania, chyba że porównania są akurat bardzo kosztowne.
Chodzi ci o samo wykonanie porównania czy i jest mniejsze od N wewnątrz tego rombu? Tego w ogóle nie bierz pod uwagę.
A tak jak mówiłem, N+N-1 i N+N wyjdzie na to samo, więc nie wiem co za różnica.

[Deltamir]

@asciiterror ok, czyli jak dobrze rozumiem:
(N+N-1) <- ILOŚĆ OPERACJI W PIERWSZEJ PĘTLI
1 - ILOŚĆ OPERACJI W DRUGIEJ (pojedyncze przejście)

Więc:

Funkcja złożoności (N+N-1)+1= O(2N)=O(N)

Dobrze?

[asciiterror]

@Deltamir: zakładając że to prawda:

(N+N-1) <- ILOŚĆ OPERACJI W PIERWSZEJ PĘTLI

1 - ILOŚĆ OPERACJI W DRUGIEJ (pojedyncze przejście)

[Deltamir]

@asciiterror Dzięki w takim razie. Teraz już wszysko wiem co i jak :)

[kafapre]

@Deltamir: nie 5 obrotów a 6, bo warunek 3<=3 jest prawdziwy i kod pętli jest wykonywany.