Как рассчитать биг-тета

Question

Может ли кто-нибудь дать мне пример реального времени для вычисления большого тета.

Является ли большая тета чем-то вроде среднего случая, (мин-макс) / 2?

Я имею в виду(минимальное время - большой O) / 2

Пожалуйста, поправьте меня, если я ошибаюсь, спасибо

Answer 1

Нотация Big-theta представляет следующее правило:

Для любых двух функций f(n), g(n), если f(n)/g(n) и g(n)/f(n) ограничены, так как n увеличивается добесконечность, тогда f = Θ(g) и g = Θ(f).В этом случае g является одновременно верхней и нижней границей роста f.

Вот пример алгоритма:

def find-minimum(List) 
  min = +∞
  foreach value in List 
    min = value if min > value
  return min

Мы хотим оценить функцию стоимости c(n), где n - размер списка ввода.Этот алгоритм выполнит одно сравнение для каждого элемента в списке, поэтому c(n) = n.

c(n)/n = 1, который остается ограниченным, когда n уходит в бесконечность, поэтому c(n) растет не быстрее, чем n.Это то, что подразумевается под обозначением big-O c(n) = O(n).И наоборот, n/C(n) = 1 также остается ограниченным, поэтому c(n) растет не медленнее, чем n.Поскольку он растет ни медленнее, ни быстрее, он должен расти с той же скоростью.Это то, что подразумевается под тета-нотацией c(n) = Θ(n).

Обратите внимание, что c(n)/n² также ограничено, поэтому c(n) = O(n²) - нотация big-O - это просто верхняя граница сложности, поэтому любая O(n) функция также O(n²), O(n³) ...

Однако, поскольку n²/c(n) = n не ограничен, то c(n) ≠ Θ(n²).Это интересное свойство бета-тета-нотации: это верхняя граница и нижняя граница сложности.

Answer 2

Большая тета - это жесткая граница для функции T(n): если: Omega(f(n))<=T(n)<=O(f(n)), то Тета (f (n)) - это жесткая граница для T (n).

Другими словамиTheta (f (n)) «описывает» функцию T (n), если и O [big O], и Omega «описывают» один и тот же T с одинаковыми f.

, например, быстрая сортировка[с правильным медианным выбором], всегда занимает максимум O (nlogn), по крайней мере Omega (nlogn), поэтому быстрая сортировка [с хорошим медианным выбором] равна Theta (nlogn)

EDIT: добавлено обсуждение в комментариях:
Поиск в массиве по-прежнему осуществляется тэтой (n).Тета-функция указывает не на худший / лучший случай, а на поведение желаемого случая.т. е. в поисках массива T (n) = количество операций в худшем случае.здесь, очевидно, T(n)<=O(n), но также T(n)>=n/2, потому что в худшем случае вам нужно перебрать весь массив, поэтому T(n)>=Omega(n) и, следовательно, Theta (n) имеет асимптотическую оценку.

Answer 3

Из http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations, мы узнаем, что «Big O» обозначает верхнюю границу, тогда как «Big Theta» обозначает верхнюю и нижнюю границу, то есть в пределе, когда n уходит в бесконечность:

f(n) = O(g(n))      -->    |f(n)| < k.g(n)

f(n) = Theta(g(n))  -->    k1.g(n) < f(n) < k2.g(n)

Таким образом, вы не можете вывести Большую Тэту из Большого О.