Как узнать, является ли алгоритм большим О или большим тета

Question

Может кто-нибудь коротко объяснить, почему алгоритм будет O (f (n)), а не Θ (f (n). Я понимаю, что это Θf (n)), это должны быть O (f (n)) и Ω (f (n)), но как узнать, является ли конкретный алгоритм Θf (n)) или O (f (n)). Я думаю, что для меня трудно не видеть большой O как худшее время выполнения. Я знаю, что это просто граница, но как она определяется. Как будто я вижу, что поиск в бинарном дереве поиска выполняется постоянно, если элемент находится в корне, но я думаю, что это не имеет ничего общего с большим O.

Answer 1

Давайте сделаем пример здесь. Представьте себе алгоритм BestSort, который сортирует список номеров, сначала проверяя, отсортирован ли он, а если нет, сортируйте его с помощью MergeSort. Этот алгоритм BestSort имеет сложность наилучшего случая Ω(n), поскольку он может обнаружить отсортированный список, а сложность худшего случая O(n log(n)), которую он наследует от Mergesort. Таким образом, этот алгоритм не имеет тета-сложности. Сравните это с чистой сортировкой Mergesort, которая всегда Θ(n log(n)), даже если список уже отсортирован.

Надеюсь, это вам немного поможет.

EDIT

Поскольку возникла путаница, я приведу некоторый псевдокод:

BestSort(A) {
If (A is sorted)  // this check has a complexity of O(n)
   return A;
else
   return mergesort(A); // mergesort has a complexity of Θ(n log(n))
}