Jaka jest różnica między O (1) i Θ (1)?

Question

Znam definicje obu z nich, ale z jakiego powodu czasami widzę O (1) i inne czasy Θ (1) zapisane w podręcznikach?

Dzięki.

Answer 1

Zapis Big-O wyraża asymptotyczną górną granicę, podczas gdy notacja Big-Theta dodatkowo wyraża asymptotyczną dolną granicę. Często górna granica jest tym, czym ludzie są zainteresowani, więc piszą O (coś), nawet gdy Theta (coś) również byłaby prawdziwa. Na przykład, jeśli chcesz policzyć liczbę rzeczy równą x na nieposortowanej liście, możesz powiedzieć, że można to zrobić w liniowym czasie i jest to O (n), ponieważ ważne dla ciebie jest to, że wygrał ' t dłużej. Jednak byłoby również prawdą, że jest to Omega (n), a zatem Theta (n), ponieważ trzeba zbadać wszystkie elementy na liście - nie można tego zrobić w czasie podliniowym.

Answer 2

O (1) i Θ (1) niekoniecznie są takie same, jeśli mówimy o funkcjach nad liczbami rzeczywistymi. Rozważmy na przykład funkcję f (n) = 1/n. Ta funkcja to O (1), ponieważ dla dowolnego n ≥ 1, f (n) ≤ 1. Jednak jest to nie Θ (1) z następującego powodu: jedna definicja f (n) = Θ (g (n)) jest granica | f (n)/g (n) | as n idzie do nieskończoności to pewna skończona wartość L spełniająca 0 < L. Podłączenie f (n) = 1/ni g (n) = 1, przyjmujemy limit | 1/n | as n idzie do nieskończoności i osiąga wartość 0. Dlatego f (n) ≠ Θ (1).

Mam nadzieję, że to pomoże!