В чем разница между O (1) и Θ (1)?

Question

Я знаю определения обоих из них, но по какой причине иногда я вижу O (1) и другие времена Θ (1), написанные в учебниках?

Спасибо.

Answer 1

Обозначение Big-O выражает асимптотическую верхнюю границу, в то время как запись Big-Theta дополнительно выражает асимптотическую нижнюю границу. Часто верхняя граница - это то, что интересует людей, поэтому они пишут O (что-то), даже когда Theta (что-то) также будет правдой. Например, если вы хотите подсчитать количество вещей, равных x в несортированном списке, вы можете сказать, что это можно сделать в линейном времени и есть O (n), потому что для вас важно, t возьмите больше, чем это. Однако также было бы верно, что это Omega (n) и, следовательно, Theta (n), так как вам нужно изучить все элементы в списке - это невозможно сделать в сублинейном времени.

Answer 2

O (1) и Θ (1) не обязательно совпадают, если вы говорите о функциях над действительными числами. Например, рассмотрим функцию f (n) = 1/n. Эта функция является O (1), поскольку для любого n ≥ 1, f (n) ≤ 1. Однако это не Θ (1) по следующей причине: одно определение f (n) = Θ (g (n)) состоит в том, что предел | f (n)/g (n) | при n переходит в бесконечность, некоторое конечное значение L, удовлетворяющее 0 < L. Подключая f (n) = 1/n и g (n) = 1, мы берем предел | 1/n | так как n переходит в бесконечность и получается, что оно равно 0. Следовательно, f (n) ≠ Θ (1).

Надеюсь, это поможет!