Dlaczego jest stwierdzenie:Czas działania algorytmu A wynosi co najmniej O (n²) - Dlaczego nie ma znaczenia?
Czas działania algorytmu A jest o co najmniej O (n²)
nie ma sensu?
Czas działania algorytmu sortowania wstawiania jest co najwyżej O (n²)
Czy jest to prawidłowe?
Próbowałem sieci, ale nie mogłem uzyskać dobrego wyjaśnienia.
mam kolejne pytanie
wiem, że każda liniowa funkcja a⋅n + b jest O (n) oraz O (n²). Czy to także O (n³)?
T(n): czas działania Algo A.Właśnie obchodzi górna granica i dolna granica T(n) stwierdzeniem: T(n) >= O(n^2)
Górna granica: Ponieważ T(n) >= O(n^2), to nie ma informacji o górnej granicy T(n) dolna granica: Załóżmy f(n) = O(n^2), to stwierdzenie: T(n) >= f(n), ale f(n) może być wszystko, co jest „mniejsza” niż n^2, Ex: constant, n,..., więc nie ma wniosek o dolnej granicy T(n) zbyt
=> stwierdzenie to jest bez znaczenia
+1 To jest poprawna odpowiedź. – chepner
Jednym z powodów może być to, że dolna granica bez górnej granicy nie jest zbyt użyteczna. "co najmniej" oznacza, że może być wykładniczy w zwykłym przypadku. Jeśli nie znasz górnej granicy, prawdopodobnie nie możesz użyć algorytmu w prawdziwej aplikacji, ponieważ nie wiesz, czy program zakończy się przed Wszechświatem.
Notacja o dużym oznaczeniu O, gdy jest używany prawidłowo, wskazuje górną granicę. Zatem stwierdzenie niższej granicy jako wielkiej litery O nadużywa notacji.
To słowo "bez znaczenia" jest mocnym słowem. Jest to z pewnością przydatna informacja, nawet jeśli nie jest odpowiednia. Mając nieco więcej kontekstu na swoje pytanie, możesz uzyskać lepszą pomoc.
Dziękuję za twoją dokładną odpowiedź. Jeśli uważam A jako algorytm sortowania wtrąceniowego, to czy warto powiedzieć "Czas działania algorytmu A wynosi co najmniej O (n2)?" W tym kontekście? – tanmoy
inna wątpliwość: Dowolna funkcja liniowa an + b jest O (n), a także jest O (n^2). Czy to także O (n^3)? – tanmoy
Tak jak powiedziałem, prawidłowe i sensowne jest określenie dolnej granicy czasu wykonania, po prostu nie należy używać do tego dużej notacji O, która jest zwykle zarezerwowana dla górnej granicy złożoności czasu. Mówienie "to co najmniej n2" jest bardziej formalnie opisane jako (duża) Omega (n^2), co oznacza "ograniczone asymptotycznie przez n^2". Więc nie powinieneś używać "O (..)", chyba że masz na myśli "ograniczony wyżej, asymptotycznie". http://en.wikipedia.org/wiki/Big_O_notation –
"Czas działania algorytmu A wynosi co najmniej O (n2)" jest równoważny "Czas działania algorytmu A to Big Omega (n2)", więc nie jest bez znaczenia.
O notacja Innymi słowy oznacza f (x) należy ustawić O (G (x)), jeżeli F (x) < C * g (x) dla wszystkich C (są liczbami rzeczywistymi)
tj Twój algorytm nie rośnie ponad funkcji kwadratowej
to nie bez znaczenia, może być wykorzystywany na przykład, jeśli nie wiesz dokładnie algorytm, ale na pewno wiem, że będzie to wymagało o (n^2) operacje.
Na przykład, jeśli nie wiemy o algorytmach sortowania, ale rozumiemy, że aby posortować tablicę potrzebujemy przynajmniej spojrzeć na każdy element, można powiedzieć, że "sortowanie tablicy to co najmniej O (n) ".
@downvoter: jakiekolwiek wyjaśnienie? –
Ponieważ nikt nie dba o to, jak szybko działa najlepiej, najgorszy przypadek jest ważny. Zwykle ludzie są zainteresowani, aby wiedzieć, ile zajmie w najgorszym przypadku.
Niech czas działania algorytmu to f(n).
=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)
Jest to zawsze prawdziwe w przypadku f(n), ponieważ czas działania jest zawsze nieujemny. Stąd oświadczenie jest zbędne.
O (n^2) jest najgorszym scenariuszem, co oznacza, że czas działania A będzie n^2 lub szybszy. Jeśli jego czas działania wynosi co najmniej O (n^2), oznacza to, że najszybszym czasem działania A jest co najmniej O (n^2). Oznacza to, że może to być cokolwiek wolniej niż O (n^2). Te stwierdzenia oznaczają, że A może mieć dowolny możliwy czas działania.
Wiem, że każda funkcja liniowa an + b jest O (n), a także O (n^2). Czy to jest również O (n^3)?
Tak, jest. Notacja big-O oznacza cały zbiór funkcji. Ale powinniśmy go używać, aby jak najlepiej scharakteryzować funkcję. Chociaż prawdą jest, że f(n) = an+b jest O(n^2) lub nawet O(n^3), dokładniej jest powiedzieć, że f(n) = O(n).
Analogia:
Stwierdzenie to jest trochę tak, jakby powiedzieć: „Dach mojego domu jest na wysokości, która wynosi co najmniej poziomu gruntu” Prawdziwe, ale całkowicie nieinformacyjne.
W jakim kontekście zadajesz to pytanie? – nhahtdh
Nie ma znaczenia, ponieważ nie podano żadnego algorytmu A. – aqua
Niech algorytm A jest algorytmem wstawiania. – tanmoy