Hej.
Czy funkcja złożoności (w najgorszym przypadku) dla rozmiaru zadania N (przyjmujemy, że M jest równe N) schematu blokowego z załącznika może wynosić F(N) = (N+N-1)+1 = 2N?
Za operację dominującą wybieram A(i) < B(j).
Dla warunku A(i) < B(j) najgorszym przypadkiem jest, gdy N razy wypadnie Nie, a N-1 Tak, co się się składa razem na (N+N-1). Dobrze odzwierciedlają to dane wejściowe A[2,4], B[1,3]. Z jest dowolną liczbą. W tym przypadku pętla A(i) < B(j) skończy pracę ze zmiennymi i = 2, j = 3 lez = 0 i warunek j > M (3 >2 ) w końcu zostanie spełniony i przejdzie do i <= N ( 2<= N) , raz się wykona i nastąpi BREAK.
Czy pominięcie B(j) < A(i), A(i) > Z oraz A(i) > Z to błąd? Wiem, że to ostatecznie przełoży się na O(N), ale mi zależy na poprawnej funkcji złożoności.
Naszło mnie dzisiaj, że może taka funkcja jaką przedstawię teraz jest poprawna: f(N) = (N+N-1)*3+2+1= (2N-1)*3+3=6N-3+3=6N.
Jedno (N+N-1) to ilość wykonań A(i) < B(j), drugie to łączna liczba B(j) < A(i) oraz A(i) > Z, a trzecie j > M. 2 to liczba wykonań i <= N (raz na tak, raz na nie) i 1 to liczba wykonań A(i) > Z.
Mam do tego wątpliwości, bo złożoność około 2N by tu pasowała, bo zrobiłem generator tablic N elementowych dla A (2,4,6,...,2N) i dla B (1,3,..., 2N-1) i dla N=10^5 wychodzi około jedna sekunda wykonywania. Natomiast dla N = 2 razy 10^5 wychodzi około 2 sekund [2N danych = 1s; 2 razy 2N danych = 2s]. Więc by pasowało, że 2 razy więcej elementów, 2 razy dłuższy czas wykonywania w przeciwieństwie do 6N.
Z góry dzięki za pomoc.