• 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

VPS Starter Arubacloud
0 głosów
848 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,311 wizyt
pytanie zadane 20 października 2015 w Algorytmy przez starzec Początkujący (410 p.)
0 głosów
1 odpowiedź 604 wizyt

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 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!

...