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

Złożoność algorytmów

VPS Starter Arubacloud
0 głosów
352 wizyt
pytanie zadane 3 lipca 2016 w Algorytmy przez Kamil95 Nowicjusz (140 p.)

Witam, mam zadańko do egzaminu. Proszę o pomoc :)

Mamy algorytm który ma złożoność n^3, zwiększamy dwukrotnie dane wejściowe. Ile razy zwiększy się złożoność obliczeniowa przy większych danych.

No więc podstawiamy pod n = 2n

Mamy (2n)^3=8n^3

Widzimy że złożoność jest 8 razy większa
I tu jest wszystko jasne, prosty jest również przykład gdzie wstępna złożoność to log n, wtedy jest ona o jakąś liczbę kroków większa. Problem pojawia się przy n log n. Przypuśćmy że rozmiar danych wejściowych również zwiększ się 2 razy. Rozpisując (2n log(n))/(n log(n)) możemy dojść do  
(2 log(n) + 2)/log(n). Tego chyba nie da się dokładnie wyliczyć. Pozostaje chyba uznać za mało istotną to "wolną" dwójkę i zaokrąglić to do 2. Proszę o pomoc :)

1 odpowiedź

0 głosów
odpowiedź 3 lipca 2016 przez Porcupine Nałogowiec (31,560 p.)
A jesteś pewien, że dokładnie o to chodziło w treści zadania? Zazwyczaj gdy rozważamy złożoność algorytmu chodzi nam jedynie o rząd złożoności np. O(n), O(n^2), O(n log n). W pierwszym przykładzie, który podałeś dochodząc do wyniku 8n^3 otrzymujemy nadal algorytm o złożoności O(n^3), co jest dość naturalne, ponieważ zwiększyliśmy wielkość danych wejściowych o stałą multiplikatywną, a jako, że jest to stała to złożoność nie zmieni swojego rzędu. Tak byłoby w każdym przypadku, niezależnie czy wychodzimy od O(n^3) czy O(n) czy O(n log n). Może bardziej o to chodziło w treści zadania?

Pozdrawiam,

Podobne pytania

0 głosów
1 odpowiedź 321 wizyt
pytanie zadane 14 czerwca 2021 w Algorytmy przez Tanormalnie Użytkownik (550 p.)
0 głosów
2 odpowiedzi 367 wizyt
pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)
0 głosów
1 odpowiedź 848 wizyt

92,454 zapytań

141,262 odpowiedzi

319,089 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!

...