Algorytm o złożoności obliczeniowej czasowej rzędu O(n*n)

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
wojtek30
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 21 cze 2017, 16:50
Płeć:

Algorytm o złożoności obliczeniowej czasowej rzędu O(n*n)

Post autor: wojtek30 » 21 cze 2017, 21:43

Witam, potrzebuje trzech przykładów algorytmów, które mają poszczególne złożoności obliczeniowe czasowe:
Algorytm o złożoności obliczeniowej czasowej rzędu O(1).
Algorytm o złożoności obliczeniowej czasowej rzędu O(n).
Algorytm o złożoności obliczeniowej czasowej rzędu O(n*n).

Do każdego algorytmu należy dodać opis analizy jego złożoności.
Liczę na Waszą pomoc bo nie wiem jak się do tego w ogóle zabrać :)

arksoftware
Rozkręcam się
Rozkręcam się
Posty: 39
Rejestracja: 24 maja 2016, 11:44
Otrzymane podziękowania: 9 razy
Płeć:

Re: Algorytm o złożoności obliczeniowej czasowej rzędu O(n*n

Post autor: arksoftware » 23 cze 2017, 09:22

Polecam książki nt. złożoności obliczeniowej algorytmów autorów takich jak Papadimitriou, Cormen, Aho, Hopcroft, Ullman, a z polskich np. Błażewicz. Wszystko jest tam dokładnie i przystępnie wyjaśnione.

Tak na szybko kilka przykładów algorytmów:
Wstawianie elementu na koniec listy dwukierunkowej - O(1)
Wyszukiwanie elementu w nieposortowanej tablicy - O(n)
Sortowanie bąbelkowe - O(n^2)
Matematyka: Generator zadań - darmowa apka dla Androida generuje losowe zadania i pokazuje pełne rozwiązania