• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność obliczeniowa - wyznaczanie wzorów na liczbę porównań

VPS Starter Arubacloud
0 głosów
1,194 wizyt
pytanie zadane 5 marca 2019 w Matematyka, fizyka, logika przez Pingui Nowicjusz (120 p.)

Cześć! 

Chciałbym poprosić was o pomoc, ponieważ od pewnego czasu na studiach męczy mnie pewne zagadnienie, z którym nie mogę sobie poradzić. Postaram się mój problem wytłumaczyć jak najlepiej, ale nie gwarantuję, że gdzieś po drodze się nie pomylę.

A więc tak: mam na studiach przedmiot, który nazywa się "Podstawy informatyki" i właściwie wszystko było w porządku, dopóki nie pojawił się temat o nazwie "Złożoność obliczeniowa algorytmów". Niestety, ze względu na niewystarczającą ilość czasu to zagadnienie nie zostało dokładnie wytłumaczone i przez to pojawił się problem. Bo o ile samą definicję złożoności powiedzmy, że rozumiem, tak nigdy nie mogę prawidłowo wykonać zadania o takiej treści:

Na podstawie fragmentu pseudokodu podaj liczbę porównań i oszacuj złożoność w sensie notacji O(·).

A tu przykładowa treść zadania:

i=0;
while(i<2*n)
{
  j=1;
  do
  {
    j=j*3;
  }while(j<4*n);
 i=i+1;
} 

Jeżeli w tym zadaniu chodziłoby TYLKO o wyznaczenie złożoności algorytmu, to jeszcze jest to przeze mnie do zrobienia. Ale niestety, oprócz tego muszę jeszcze wyznaczyć wzór na ilość porównań pętli zewnętrznej (Lz) i pętli wewnętrznej (Lw), a następnie wszystko zsumować (Lc). Takie uwarunkowanie mam podane w zadaniu:

L jest liczbą porównań, a jako rozwiązanie zadania podajemy Lw, Lz, Lc, O(·)

I powiem szczerze: nigdy nie potrafiłem wyznaczyć prawidłowych wzorów. Za każdym razem podaję odpowiedź po części dobrą (bo złożoność, co najciekawsze, zawsze podaję prawidłową), ale zadanie nie zostanie uznane, dopóki nie będzie zrobione w całości. I tu zwracam się do was o pomoc: czy mógłby mi ktoś wyjaśnić, na jakiej podstawie wyznacza się te wzory na ilość porównań? Ja wiem, że to pewnie nie jest trudne, ale naprawdę nie mogę sobie z tym poradzić. Byłbym bardzo wdzięczny za jakiekolwiek wyjaśnienie, które pozwoli mi to zrozumieć.

A, i jeśli jest to istotne, to muszę to policzyć na kartce, bez użycia komputera i kalkulatora.

1 odpowiedź

+1 głos
odpowiedź 7 marca 2019 przez Maciej Złotorowicz Gaduła (4,230 p.)

do porównania dochodzi 2 razy: 

while(i<2*n)

i tu:

}while(j<4*n);

pętla (nazwijmy ją i by nie pisać zewnętrzna i wew. ) i wykonuje się zawsze 2n razy. Ale wykona 2n+1 porównań (dlatego że (dla przykładu n = 10) na początku masz i = 0 potem 1,2,3 i tak aż i = 20 co warunku już nie spełnia.
Pętla wykona się 20 razy bo 20 razy warunek był spełniony ale porówna 21 bo warunek nie był spełniony dla 20 (20 nie jest większe od 20) więc pętla i wykona zawsze 2n porównań

z pętlą j (wew) jest więcej problemów: po pierwsze do..while sprawdza warunek na końcu pętli. więc gdy j = 1 nie sprawdza warunku. 
Znów z przykładem n = 10: dla n = 10 warunek pętli wygląda tak: j < 40 więc pętla będzie się wykonywać aż j nie osiągnie wartości większej od czterdziestu  + 1. w kolejnych iteracjach pętli, zmienna j przyjmuje wartości kolejnych potęg 3. 
j = 3, j = 9, j = 27, j = 81 ...
a więc dla n = 10:
3 < 40
9 < 40
27 < 40
81 < 40 FAŁSZ! 
więc dla n = 10 pętla wykonała się 4 razy. warunek można zapisać ładniej tak:
3^x < 4n (x ilość iterancji)
szukamy miejsca gdzie warunek "zmieni" stan (czyli miejsce zerowe):
3^x - 4n = 0 ; obliczamy względem x 
x = log3(4n)
zaokrąglając w góre:
x = ceil(log3(4n))
a więc teraz podstawiając pod n jakąś liczbę otrzymasz ilość iteracji która się wykona.

Mam nadzieje że mając te dane wiesz jak policzyć sumaryczną ilość porównań? 

Nie dam sobie ręki uciąć że wszystkie te obliczenia są poprawne!  na 98% tak ale lepiej niech mnie ktoś jeszcze sprawdzi.   

komentarz 9 marca 2019 przez Pingui Nowicjusz (120 p.)
Dobra, chyba zaczynam coś ogarniać, bo robię już sam obliczenia i wydaje mi się, że wychodzi mi dobrze. A twoje obliczenia też są prawidłowe, bo w piątek prowadzący pokazywał nam rozwiązanie i wyszło tak samo, jak tobie.

Czyli jest w porządku, powinienem już sobie dalej poradzić, ale poćwiczę to jeszcze, bo muszę być dobrze przygotowany do kolosa. Dziękuję bardzo za pomoc, w końcu ktoś mi wytłumaczył, jak to się powinno robić krok po kroku. Jeszcze raz, wielkie dzięki!

Podobne pytania

+1 głos
1 odpowiedź 322 wizyt
0 głosów
0 odpowiedzi 584 wizyt
pytanie zadane 16 września 2019 w C i C++ przez stim4pl Nowicjusz (170 p.)
0 głosów
1 odpowiedź 482 wizyt

92,417 zapytań

141,222 odpowiedzi

318,985 komentarzy

61,831 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...