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

Złożoność czasowa algorytmu - Matura próbna 2020

Aruba Cloud - Virtual Private Server VPS
0 głosów
1,173 wizyt
pytanie zadane 7 stycznia 2021 w Algorytmy przez iglo89 Nowicjusz (120 p.)
Witam,

Podczas przeglądania arkuszy maturalnych z informatyki natknąłem się na zadanie polegające na określeniu rodzaju złożoności czasowej algorytmu podanego w zadaniu. Stąd pytanie: na jakiej podstawie wyznacza się ów rodzaj? Odpowiedź to sześcienna, kwadratowa, liniowa lub logarytmiczna. Ze źródeł dostępnych w internecie wynikają jakieś wzory, których nie rozumiem, więc proszę o pomoc wszystkich mających wiedzę na ten temat.

Problem wystąpił przy robieniu zadania 1.3 z matury próbnej z informatyki, kwiecień 2020.

Pozdrawiam.

1 odpowiedź

0 głosów
odpowiedź 7 stycznia 2021 przez tmar1212 Bywalec (2,600 p.)
Widać, że dane po każdym wywołaniu dzielą się na pół; to się domyśl jaka jest złożoność. Dowód znajdziesz w każdym podręczniku.
komentarz 7 stycznia 2021 przez iglo89 Nowicjusz (120 p.)
Odpowiedź według CKE to logarytmiczna, tylko nie bardzo czaję co ten algorytm ma do logarytmu. Na jakiej podstawie w takim razie ta odpowiedz jest prawidłowa? Z definicji w/w rodzajów złożoności nie wynika zbytnio nic, bądź ja nie widzę zależności. Wiec ponawiam pytanie: na jakiej zasadzie mam przeanalizować algorytm, aby rozstrzygnąć jaki jest rodzaj złożoności? Jak wykonać takie zadanie?
komentarz 7 stycznia 2021 przez tmar1212 Bywalec (2,600 p.)
To jest szybkie pytanie, takie rzeczy powinno się wiedzieć, (jak za każdym wywołaniem rekurencyjnym dane zmniejszają się o połowe, to złożonośc jest logarytmiczna). Złożoność ocenia się analizując algorytm, (jak myślisz skąd to wiedzialem, zgadłem? Nie, przeanalizowałem zadanie 1.3) lub/i rozwiązując rekurencję. Dla przykładu wyżej wymieniony algorytm jest równoważny wyszukiwaniu binarnemu:

https://www.google.com/search?safe=off&sxsrf=ALeKk01NPRBvt6oYiH5cD3xy4S8QfDGRnA%3A1610050494679&source=hp&ei=vmv3X-LFJrLmgweO4ajACQ&q=solve+binary+search+recurrence+relation&oq=solve+binary+search+recurrence+&gs_lcp=CgZwc3ktYWIQAxgAMgUIABDJAzoHCCMQ6gIQJzoECCMQJzoICAAQyQMQkQI6BQgAEJECOgQIABBDOgIIADoHCAAQyQMQQzoICC4QxwEQowI6AgguOggILhDHARCvAToFCAAQywE6CwguEMcBEK8BEMsBOgUILhDLAToICAAQyQMQywE6BAgAEAo6BggAEBYQHjoICAAQFhAKEB5Q7BVY_Elg_1FoAXAAeACAAZ0CiAGgJZIBBjAuMjcuNJgBAKABAaoBB2d3cy13aXqwAQo&sclient=psy-ab
komentarz 7 stycznia 2021 przez iglo89 Nowicjusz (120 p.)
1. Jestem w 4 technikum i jakoś nie miałem poruszanych 90% rzeczy potrzebnych do wykonania zadań na maturze, więc stwierdzenie, że powinienem to wiedzieć jest niepotrzebne i nic mi nie daje.

2. Że złożoność algorytmu określa się poprzez jego analizę zawarłem już w pytaniu, ale nie wiedząc co znaczy dany termin to mogę sobie analizować w nieskończoność. Co mi da analiza, jak nigdzie nie mogę znaleźć zrozumiałego tłumaczenia czym jest złożoność liniowa lub kwadratowa?

3. Teraz wiem tyle, że jak jest dzielenie przez 2 w algorytmie to jest to logarytmiczna. Co dalej? Jak rozpoznać liniową itd.?
komentarz 7 stycznia 2021 przez tmar1212 Bywalec (2,600 p.)
Wypożycz sobie CLRS i poczytaj.
komentarz 7 stycznia 2021 przez iglo89 Nowicjusz (120 p.)
Otrzymałem od Pana/Pani 3 odpowiedź, a tego o co proszę ciągle brak. Prosiłem o przedstawienie jak rozróżnić złożoności, lub o źródło z którego się tego dowiem. Proszę nie tracić swojego cennego czasu na pokazaniu mi, że powinienem to wiedzieć, bo gdybym wiedział, to bym nie pytał.

Pozdrawiam i miłego wieczoru ;)
komentarz 7 stycznia 2021 przez tmar1212 Bywalec (2,600 p.)
Złożoność to jest spory dział matematyki stosowanej, nie ogarnę tego w komentarzu. Jak chcesz wiedzieć więcej, to musisz się douczyć.
komentarz 7 stycznia 2021 przez iglo89 Nowicjusz (120 p.)
Jasne, ale ten termin dzisiaj zobaczyłem po raz pierwszy i nie wiem nawet od czego zacząć. Jakieś dobre źródło, najlepiej dostępne w internecie? Chciałbym ogarnąć to jak najszybciej a na pomoc szkoły liczyć nie mogę.
komentarz 7 stycznia 2021 przez tmar1212 Bywalec (2,600 p.)

Podobne pytania

0 głosów
5 odpowiedzi 2,656 wizyt
pytanie zadane 20 października 2015 w Algorytmy przez starzec Początkujący (410 p.)
0 głosów
1 odpowiedź 904 wizyt

93,331 zapytań

142,323 odpowiedzi

322,400 komentarzy

62,664 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

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...