Czy

11

Mam więc pytanie, aby udowodnić stwierdzenie:

O(n)Θ(n) ...

Nie muszę wiedzieć, jak to udowodnić, po prostu myślę, że to nie ma sensu i myślę, że powinno raczej być tak Θ(n)O(n) .

Rozumiem, że O(n) jest zbiorem wszystkich funkcji, które nie działają gorzej niż n podczas gdy Θ(n) jest zbiorem wszystkich funkcji, które nie działają lepiej i nie gorzej niż n.

Korzystając z tego, mogę wymyślić przykład funkcji stałej, powiedzmy g(n)=c . Ta funkcja z pewnością będzie elementem O(n) ponieważ nie będzie gorsza niż n gdy n zbliży się do wystarczająco dużej liczby.

Jednakże, funkcje te same nie byłoby elementu Θ ( n ), a g jest lepiej niż n o dużej n ... A ponieważ g O ( n ) i g Θ ( n ) , a następnie O ( n ) Θ ( n )gΘ(n)nngO(n)gΘ(n)O(n)Θ(n)

Czy to pytanie może być błędne? Nauczyłem się, że takie założenie jest niebezpieczne i zwykle coś przeoczyłem, po prostu nie widzę, co to może być w tym przypadku.

Jakieś pomysły ? Wielkie dzięki..

Rawb
źródło
5
Pomyśl o . następnie f = O ( n ), ale f Θ ( n ) . Więc „ O ( ) ” jest słabszym popytem, ​​dlatego zawiera więcej funkcji ..fa=0fa=O(n)faΘ(n)O()
Ran G.
5
Myślę, że masz rację, wydaje się, że to pomyłka.
Yuval Filmus,
3
Co rozumiesz przez zapis : podzbiór lub odpowiedni podzbiór? Radzę używać lub ⊊, aby uniknąć nieporozumień.
A.Schulz,

Odpowiedzi:

11

Za sugestią Rafaela zamieściłem poprzedni komentarz w tę odpowiedź.

Nie jest prawdą, że . W rzeczywistości z definicji. Mamy więc .Θ ( f ( n ) ) = O ( f ( n ) ) Ω ( f ( n ) ) Θ ( f ( n ) ) O ( f ( n ) )O(fa(n))Θ(fa(n))Θ(fa(n))=O(fa(n))Ω(fa(n))Θ(fa(n))O(fa(n))

Patrick87
źródło
4

Pomyśl o tym w ten sposób: każda funkcja, która działa „nie gorzej niż n” i „nie lepiej niż n”, jest również funkcją, która „nie gorzej niż n”. Część „nie lepiej niż n” to tylko dodatkowe ograniczenie. Jest to proste zastosowanie reguły logicznej, która mówi: . Zgodnie z tym rozumowaniem wszystkie funkcje znajdujące się w zbiorze Θ ( n ) są również elementami zestawu O ( n ) .xyxΘ(n)O(n)

saadtaame
źródło