Возьмем, к примеру, бинарный поиск. Лучшее время выполнения будет получено при первом сравнении, когда
key_to_find == (imin + imax)/2;
И в лучшем случае время выполнения будет представлено O (1). Я полностью это понимаю, но меня смущает, почему используется O (1) и почему я не могу использовать (1) или любую другую запись для того же.
т.е. Как определить, какую нотацию следует использовать для представления времени выполнения (лучший, средний или наихудший случай).
O-обозначение и Θ-обозначение не имеют прямого отношения к лучшему, среднему или худшему случаю. Они используются для асимптотических оценок функций. Вы можете написать: 47n lg n = O(n lg n), 3n^2 + 4n = O(n^2)
И есть разница между обозначениями O и Θ. O означает «не более (с использованием некоторого постоянного множителя)», Θ означает «равно (с использованием некоторого постоянного множителя)», например: 47n ln n = O (n ^ 2), но это не Θ (n ^ 2).
Если вы хотите выразить лучший случай, средний случай или худший случай, вы обычно записываете их явно: «Лучший случай — O(1) (или Θ(1)), средний случай — O(lg n), худший случай — O( н)».
Иногда вы также «время работы равно O (x)», тогда вы имеете в виду, что время работы самое большее пропорционально x. Если вы говорите, что «время работы равно Θ(x)», то вы имеете в виду, что время работы всегда пропорционально x.
Вы можете использовать любые обозначения. Big Theta является наиболее точным, поэтому вы должны использовать его всякий раз, когда вы его знаете. В качестве примечания, O (1) эквивалентно Θ (1) в контексте анализа сложности (где количество операций является целым числом, т. Е. Нельзя иметь O (1 / n) как сложность).
