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

Złożoność czasowa algorytmu - problem ze zrozumieniem

VPS Starter Arubacloud
0 głosów
2,311 wizyt
pytanie zadane 20 października 2015 w Algorytmy przez starzec Początkujący (410 p.)

Cześć wszystkim!
Chciałbym prosić Was o pomoc w zrozumieniu zagadnienia złożoności czasowej. Domyślam się, iż jest to podstawa całej algorytmiki, dlatego brak wiedzy na ten temat skreśla moją przyszlość związaną z pisaniem dobrych algorytmów, bo wiadomo można klepać dużo, ale moża też mądrze :)

Otóż sam problem pojawił się już na wykładzie. Intuicyjnie domyślam się, iż chodzi o liczbę instrukcji która wykonała się w danym algorytmie, a także, że zależna jest ona od zmiennych wejściowych.

Myśle, że zrozumiem o na tym przykładzie:

zrzut ekranu

Problemem jest liczba instukcji, nie rozumiem skąd się wzięła, mimo że rozumiem algorytm. Chciałbym prosić was o poprowadzenie mnie "za rączkę" podczas liczenia.

 

Pozdrawiam :)

5 odpowiedzi

+1 głos
odpowiedź 21 października 2015 przez Benek Szeryf (90,690 p.)
Ja Cię za rękę nie poprowadzę, ale mogę na szybko polecić Ci: http://wazniak.mimuw.edu.pl/index.php?title=Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa
+1 głos
odpowiedź 5 listopada 2015 przez Darellur Nowicjusz (220 p.)

Przykład 1 (pesymistyczny): 4(liczba operacji, które zostaną wykonane niezależnie od wielkości wczytanych danych tj. Czytaj n, czytaj mx, jeden raz Jeżeli n=1 i wypisz mx)+5(ilość operacji na iterację w przypadku, gdy n za każdym razem jest większe od mx) (n-1) (ilość iteracji; -1 jest, bo przy n=1 nie dochodzi do tych 5 operacji)

Przykład 2 (optymistyczny): 4(liczba operacji, które zostaną wykonane niezależnie od wielkości wczytanych danych tj. Czytaj nczytaj mx, jeden raz Jeżeli n=1 i wypisz mx)+4(ilość operacji na iterację w przypadku, gdy n za każdym razem jest mniejsze od mx)(n-1)(ilość iteracji; -1 jest, bo przy n=1 nie dochodzi do tych 4 operacji)

Wniosek: Algorytm jest niestabilny.

0 głosów
odpowiedź 21 października 2015 przez starzec Początkujący (410 p.)
Nikt nie jest w stanie pomóc? :c
0 głosów
odpowiedź 21 października 2015 przez event15 Szeryf (93,790 p.)

Domyślam się, iż jest to podstawa całej algorytmiki, dlatego brak wiedzy na ten temat skreśla moją przyszlość związaną z pisaniem dobrych algorytmów, bo wiadomo można klepać dużo, ale moża też mądrze

Źle się domyślasz. Nawet nie wiesz jak kiepskie kody powstają za grube pieniądze. Wcale nie jest to żadna podstawa algorytmiki. Złożoność obliczeniowa czy czasowa to po prostu jeden z działów, który jest powiązany z optymalizacją. 

W algorytmach myślenie jest najważniejsze. Rozwiązywanie problemów. Żeby rozwiązać jakiś problem możesz sobie zrobić zawiłe rozwiązanie - nikt Ci nie broni, skoro to działa (zawsze to jakas wartość biznesowa). A to, czy to będzie optymalne czy nie to będzie zależec od Twojego doświadczenia i dupogodzin przy pisaniu programów. 

 

Możliwe, że to pomoże:

http://eduinf.waw.pl/inf/utils/010_2010/0216.php

 

 

 

0 głosów
odpowiedź 10 stycznia 2017 przez morele123 Gaduła (4,790 p.)
Jak liczysz złożoności to nie obchodzą cię stałe. Interesujesz się tylko zmiennymi dominującymi, czyli tymi co wchodzą na wejściu i ile razy się wykonają pętle w najgorszym przypadku. Jeżeli nie ma żadnych pętli, są tylko operacje, które zawsze wykanają się określoną ilość razy to masz zlożoność O(1), W tym twoim przypadku to wchodzisz do pętl przy sprawdzeniu n=1, no i zakładasz, że tak nie jest najgorszy przypadek, i co się wykona wtedy, a no wczyta ci się a, to 1 operacja, potem operacja porównania, która wprawsza czy a większa od mx, czyli też 1 operacja, no i albo się wykona przypisanie, albo odrazu odejmie od n 1 czyli zakładamy najgorszy scenariusz, czyli, że przypisze i będzie więcej operacji. Oszacowując mamy, więc złożoność liniową, bo nigdzie nie ma dwóch pętli, a jedna pętla która się wykona w całości n-1 razy. Jeżeli chcesz policzyć dokładne oszacowanie to jak masz pętle, która sięwykona n razy a w tej pętli operacje jakieś to sumujesz te operacje i mnożysz przez to ile razy wykona się pętla.

Podobne pytania

0 głosów
1 odpowiedź 848 wizyt
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!

...