szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 wrz 2017, o 15:28 
Użytkownik

Posty: 10
Lokalizacja: Polska
Pewien algorytm o dwóch danych wejściowych m oraz n, które są liczbami naturalnymi, składa się z następujących kroków:
1) Krok początkowy o stałej liczbie czynności obliczeniowych.
2) Dla j = 1,…, m powtarzaj czynności obliczeniowe o złożoności O(n).
3) Jeżeli wyniki uzyskane w kroku 2) spełniają pewien warunek, wykonaj czynności
obliczeniowe o złożoności O(\log n); w przypadku przeciwnym wykonaj inne czynności
obliczeniowe o złożoności O(n \cdot \log m).
4) Po wykonaniu kroku 3) algorytm kończy się.
Podaj i uzasadnij, jaka jest złożoność obliczeniowa przedstawionego algorytmu?
Góra
Mężczyzna Offline
PostNapisane: 27 wrz 2017, o 09:00 
Gość Specjalny

Posty: 5793
Lokalizacja: Toruń
Przeanalizuj po kolei, co się dzieje. Złożoność to O(nm).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 matematyka dyskretna_iloczyn kartezjański oraz indukcja  barbossa19  1
 Matematyka dyskretna. Zadania z rekurencji  lllukasll  4
 Algorytm doboru kombinatoryki szkoła średnia  calculus  4
 Algorytm wież Hanoi  nedroxn  0
 Algorytm rozwiązujący problem  damianel  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl