Schemat blokowy - JS

[patryk2205 1]

Cześć,

Czy mógłbym prosić o zerknięcie na poniższy schemat blokowy? Schemat blokowy skonstruowałem na podstawie kodu(kod znajduje się w linku, schemat blokowy w dysku google). Program ogólnie wyznacza ilość powtórzeń zadanej wartości w posortowanej tablicy. Ostatnio udało mi się napisać program a teraz zrobiłem do niego schemat blokowy chociaż nie jestem pewny czy poprawnie.

https://codepen.io/patryk2205/pen/RwobWmB

https://drive.google.com/file/d/1GucODgMz5l4JdXWJE6dR3FjAA5lWOVJd/view?usp=sharing

[Karister 1533]

Masz ten sam błąd w programie i na diagramie. Nie zadziała dla liczby, której nie ma w tablicy. Przecież -1 to znaleziony (a raczej nieznaleziony) indeks, co oznacza, że szukana liczba w tablicy występuje 0 razy, a nie -1 razy. Co do kodu - nie ma sensu przekazywać rozmiaru tablicy jako argumentu funkcji - można ją pobrać dopiero tam, gdzie jest potrzebna.

Edytowane 28 Stycznia 2021 przez Karister

[patryk2205 1]

Co do tego wypisywania -1 to już inna kwestia, wystarczy dać warunek jeśli inMin == -1 i tyle. Już wiem w czym rzecz.

Mam teraz drugą sprawę, potrzebują policzyć złożoność czasową tego programu, chodzi o same te funkcje. Wiem, że wynosi ono O{logn} ale muszę to rozpisać jakoś. Pierwsze pytanie, jaki będzie najgorszy przypadek dla tego algorytmu? Wiem, że np. dla funkcji pierwszy() najgorszą sytuacją było by gdyby funkcja przeszukała całą tablicę i nie znalazła by szukanego elementu, ale tutaj mamy jeszcze drugą funkcję, która szuka ostatniego wystąpienia więc najgorszą sytuacją będzie po prostu istnienie elementu szukanego w tablicy? Wtedy algorytm będzie musiał wykonać dwie funkcje zamiast jednej o to jest chyba większa złożoność czasowa niż jakby miała się wykonać tylko jedna funkcja. Chciałbym to rozpisać w sposób podobny jak na filmiku:

 

Tylko tutaj mam ciężej bo nie wiem jak sobie poradzić ze złożonością czasową gdy mam kilka funkcji. Chociaż tutaj wracam do punktu wyjścia i zwracam się z zapytaniem jaki byłby najgorszy scenariusz bo taki trzeba rozpatrzeć gdy liczymy złożoność czasową

[Karister 1533]

Binary search zawsze zmniejsza przeszukiwany zbiór o połowę, więc jego złożoność pesymistyczna to również O(logN). Nie ma znaczenia, czy wykonujesz kolejno taki algorytm raz, dwa, czy pięć razy. O(xlogN) to nadal jest O(logN).

Żeby dostać złożoność liniową O(N), musiałbyś na przykład:

• zmienić na linowy sposób ograniczania domeny w kolejnych iteracjach: f = f(n-x), x dowolne
• funkcja rekurencyjna dzieląca domenę na pół w każdej iteracji, musiałaby wołać samą siebie dwa razy: f =  f(n/2) + f(n/2)

W obu przypadkach oczywiście gdzieś musiałby być warunek kończący.

Edytowane 29 Stycznia 2021 przez Karister

[patryk2205 1]

Ok, ale jak na przykład liczyć złożoność kiedy program na trzy funkcje a nie jedną jak na filmiku. Wtedy muszę szukać najgorszych przypadków dla każdej funkcji z osobna? Bo muszę to jakoś rozpisać.

Np. dla funkcji licz() będę miał wartość stałą

		function licz(tab, w, n)
		{
			
			idMin = pierwszy(tab, 0, n-1, w, n); ----   t1
			
																		 t - const.
			if (idMin == -1){return idMin}; ----- t2			         L(n) = t1 + t2 + t3 + t4 + t5 = t
			
		
			idMax = ostatni(tab, idMin, n-1, w, n); ---> t3
			ile = idMax-idMin+1; --> t4
		
			return ile; --> t5 
		}

A dla funkcji policzył bym dla najgorszego możliwego przypadku czyli gdy szukanej wartości w ogóle nie ma czyli tak samo jak na filmie wyżej:

function pierwszy(tab, l, p, w, n) 
		{
			if(l <= p) ----> c1
			{
				mid = Math.floor((l+p)/2); --> c2
				
				if((mid == 0 || w  > tab[mid-1])&&(tab[mid] == w)) c3	
				{														c - constants
					return mid; ---> c4									G(n) = c1 + c2 + c3 + c4 + c5 + G(n/2) = c + G(n/2)
				}														G(n/2) = c + G(n/4)
																		----------
				else if(w > tab[mid])									G(n) = 2c + G(n/4)
				{														G(n/4) = 2c + G(n/8)
					return pierwszy(tab, (mid+1), p, w, n);				----------
				}														G(n) = 4c + G(n/8)
				else													Pattern: G(n) = ic + G(n/2^i)
				{														G(n/2^i) = G(1) // podczas wykonywania funkcji zostanie jeden element do sprawdzenia
					return pierwszy(tab, l, (mid-1), w, n);				n/(2^i) = 1 => n = 2^i => log_2(n) = i
				}														G(n) = c*log_2(n) + G(n/2^log_2(n)) = c*log_2(n) + G(n/n) = c*log_2(n) + G(1) = z + clog_2(n)
																		G(n) = log_2(n)
			}
			return -1; ---> c5
		}

Wypadało by jeszcze policzyć dla funkcji ostatni() ale tutaj nie ma raczej najgorszej sytuacji.... I na koniec wypadało by dodać te czasy z trzech funkcji i ostatecznie podać big O(....)

[Karister 1533]

To nie ma znaczenia, ile funkcji ma program. Możesz go podzielić na 100 funkcji i złożoność obliczeniowa pozostanie ta sama. Liczy się złożoność algorytmu - a tu masz dwa razy wykonany algorytm binary search, który ma O(logN). Wykonujesz go dwa razy, więc jest O(2logN), czyli po prostu O(logN). Wszystkie pozostałe operacje w tym kodzie mają O(1), więc zostaje czynnik dominujący, bo O(logN) + O(1), to wciąż O(logN). A liczenie złożoności obliczeniowej binary search formalnym sposobem już wygooglowałeś.

Edytowane 29 Stycznia 2021 przez Karister

[patryk2205 1]

Ok, rozumiem. Dzięki. Jeszcze jedno pytanie, jaka jest tutaj operacja dominująca(elementarna)? Czy jest to l <= p ?

[Karister 1533]

Nie, to porównanie nie ma w ogóle znaczenia z punktu widzenia złożoności obliczeniowej. Dominujące jest przeszukiwanie tablicy przy pomocy binary search.

Edytowane 29 Stycznia 2021 przez Karister

[patryk2205 1]

Czyli uogólniając:

Operacja dominująca w funkcji pierwszy() to:

if((mid == 0 || w  > tab[mid-1])&&(tab[mid] == w)) //mid == 0 gdy tablica ma 1 element
                {
                    return mid; // zwraca indeks pierwszego wystapienia
                }
                else if(w > tab[mid])
                {
                    return pierwszy(tab, (mid+1), p, w, n);
                }
                else
                {
                    return pierwszy(tab, l, (mid-1), w, n);
                }

if((mid == 0 || w  > tab[mid-1])&&(tab[mid] == w)) //mid == 0 gdy tablica ma 1 element
				{
					return mid; // zwraca indeks pierwszego wystapienia
				}
				else if(w > tab[mid])
				{
					return pierwszy(tab, (mid+1), p, w, n);
				}
				else
				{
					return pierwszy(tab, l, (mid-1), w, n);
				}

Natomiast w funkcji ostatni():

if((mid2 == n-1 || w < tab[mid2+1]) && (tab[mid2] == w))
			{
				return mid2; //zwraca indeks ostatniego wystąpienia
			}
			else if(w < tab[mid2])
			{
				return ostatni(tab, l, (mid2-1), w, n);
			}
			else
			{
				return ostatni(tab, (mid2+1), p, w, n);
			}

Zgadza się?

[Karister 1533]

Całe funkcje do szukania pierwszego i ostatniego elementu są dominujące z punktu widzenia złożoności obliczeniowej. One implementują rekurencyjny algorytm, który definiuje tu, ile razy wykona się kod. Kluczowe fragmenty kodu to ten, co wylicza mid i potem woła sam siebie rekurencyjnie dla połowy zakresu. To jest to, co implementuje strategię dziel i zwyciężaj i powoduje, że jest O(logN).

[patryk2205 1]

Ok, dzięki wielkie. Sporo rzeczy mi rozjaśniłeś. Miałbym jeszcze jedno pytanie, chciałem zrobić opis słowny tego algorytmu, ale w internecie nie znalazłem żadnych opisów bardziej złożonych algorytmów i tak właściwie nie wiem co powinien zawierać taki opis. Powinienem opisywać krok po kroku co robi algorytm? Np.

2. Pobierz tablicę uporządkowaną niemalejąco, wartość, której ilość powtórzeń algorytm ma znaleźć oraz długość pobranej tablicy
3. Sprawdź czy indeks początkowy listy jest mniejszy lub równy ostatniemu indeksowi listy. Jeśli jest wykonaj 3.1 jeśli nie, przypisz indeksowi pierwszego wystąpienia wartość -1 i wykonaj 4.
3.1 Oblicz środkowy indeks licząc średnią arytmetyczną indeksu początkowego i końcowego
3.2 Sprawdź czy indeks środkowy jest równy 0 lub wartość szukana jest większa od elementu tablicy o indeksie o 1 mniejszym od środkowego i czy środkowy element jest równy szukanej wartości. Jeśli tak, wykonaj 4. w przeciwnym razie wykonaj 3.2.1 ..........................