Skocz do zawartości
patryk2205

Schemat blokowy - JS

Rekomendowane odpowiedzi

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
Napisano (edytowane)

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 przez Karister

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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ą

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
Napisano (edytowane)

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 przez Karister

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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(....)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
Napisano (edytowane)

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 przez Karister

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
Napisano (edytowane)

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 przez Karister

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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ę?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

 

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

  • Popularne aktualnie

  • Tematy

  • Odpowiedzi

    • Te pompy alphacoola mają średnie opinie. Były bardzo problematyczne. 
    • oba zabezpieczenia, które podaliście to absolutny bezsens. Co to za zabezpieczenie, liczenie 10 - 30 sec od zakupu? A jak ktoś zdąży przejść checkout w ten czas to też go odrzucisz? Captcha w dzisiejszych czasach jest wbrew zasadom dostępności stron internetowych, a poza tym rozwiązanie jej jest bajecznie proste. Ciężko jest poprawnie wyblokować boty i trzeba korzystać z połaczenia kilku rozwiązań, poza tym jaki byłby cel biznesowy sklepu internetowego przy blokowaniu botów?
    • Mi nawet orange wywaliło komunikat xd. Chyba 1 raz w życiu widzę takie coś od orange lol. 
    • https://allegro.pl/oferta/karta-graficzna-asus-geforce-gtx-1070-strix-8-gb-10438002921 https://allegro.pl/oferta/karta-graficzna-asus-gtx1070-strix-oc-8gb-10435887196 Najtańsza obecnie oferta to https://allegro.pl/oferta/karta-graficzna-asus-geforce-gtx-1070-8-gb-gddr5-10452776708 Więc możesz sobie wystawić licytacje od 1zł, lub kup teraz za np 1749zł.
    • obejrzałem sobie ten gameplay 25-minutowy i mam mieszano chłodne odczucia, nie mam na mysli ze to co widziałem było złe bo nie było, widac ze twórcy starali sie odrobine trzymac ograniczeń uniwersum ale zeby zachowac choc troche roznorodnosci wprowadzono rózne typy obcych, jest pare rodzajów broni, są oczywiscie działka sentry (znane z wersji directors cut filmu ALIENS)...rozni obcy mają rozne parametry np wojownicy są wolni ale mają sporo życia i potrafią powalic na ziemie albo chwycic i podniesc w górę żołnierza. Grafika jest zadowalająca jak na sieciową strzelanine. Mimo powyższego jednak sama rozgrywka mnie nie porwała, wszystko sprowadza sie ciągle do tego zeby dojsc do jakiegos punktu (np windy) ,i zanim sie nacisnie magiczny button trzeba sie "okopać" czyli zabezpieczyc teren, potem oczywiscie wyskakuje pare fal obcych po rozwaleniu których mozemy isc dalej i tak generalnie to wygląda cały czas. Wydaje mi sie ze same gameplay jest zbyt mało urozmaicony by na dłuższą mete nie nudził (gameplay wydaje sie mocno statyczny, to nie ta dynamika i movement co w apexie czy doomie, tutaj sprawdza sie trzymanie sie w kupie obok działka sentry i pilnowanie punktów przyjscia obcych co oczywiscie jest skuteczne ale na dłuższą mete mocno nuuudne)  
  • Aktywni użytkownicy

×
×
  • Dodaj nową pozycję...