Funkcja złożoności dla najgorszego przypadku

Odpowiedz Nowy wątek
2019-01-22 22:14

Rejestracja: 1 rok temu

Ostatnio: 9 miesięcy temu

0

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.

edytowany 3x, ostatnio: Dande, 2019-01-23 09:09

Pozostało 580 znaków

2019-01-23 16:46
Moderator

Rejestracja: 12 lat temu

Ostatnio: 1 godzina temu

0

Złożoność obliczeniowa pomija stałe, więc jeśli czas wykonania to f(n) = 2n lub f(n) = 6n to oba należą do klasy złożoności O(n).

A w tym przypadku to tak, nie masz pętli wewnątrz pętli, więc złożoność przedstawionego algorytmu (przy założeniu, że wszystkie bloczki mają złożoność O(1)) to O(n).


edytowany 1x, ostatnio: hauleth, 2019-01-23 16:47

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0