szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 wrz 2017, o 14: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 08:00 
Gość Specjalny

Posty: 5874
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 - 2 pytanka  sachkan  4
 Zasada szufladkowa + potęgi(mat. dyskretna)  p_lipa  2
 algorytm wielomianowy - prawdopodobnie przepływy  TrzyRazyCztery  6
 algorytm wyszukania binarnego  opolak  0
 Liczby Armstronga - algorytm  michal_2  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl