Witam,
zastanawiam się, czy dobrze myślę:
jeżeli algorytm działa w przybliżeniu jako funkcja 2n to górnymi oszacowaniami są:
\(O(n^2)\)
\(O(nlogn)\)
\(O(nlog^2n)\)
?
Oszacowanie z góry
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
Karol_2015
- Rozkręcam się
- Posty: 30
- Rejestracja: 15 lis 2015, 18:44
- Podziękowania: 6 razy
-
arksoftware
- Rozkręcam się
- Posty: 39
- Rejestracja: 24 maja 2016, 11:44
- Otrzymane podziękowania: 9 razy
- Płeć:
Tak, ale jeśli twój algorytm ma złożoność liniową (2n) dla każdej instancji problemu, to górnym oszacowaniem jest też \(O(n)\).
W praktyce podawanie wyższego oszacowania niż minimalne ma sens chyba tylko podczas przeprowadzania dowodu tego minimalnego oszacowania.
W praktyce podawanie wyższego oszacowania niż minimalne ma sens chyba tylko podczas przeprowadzania dowodu tego minimalnego oszacowania.
Matematyka: Generator zadań - darmowa apka dla Androida generuje losowe zadania i pokazuje pełne rozwiązania