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

Question

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

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

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

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

Answer 1

Биг-тэта нотация представляет собой следующее правило:

Для любых двух функций 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)), тогда Theta (f (n)) является точной оценкой для T(n).

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

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

РЕДАКТИРОВАТЬ: добавил обсуждение в комментариях:
Поиск в массиве - это все еще Theta(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 мы узнаем, что "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)

Таким образом, вы не можете сделать вывод о большой тэте из Big O.

Answer 4

Обозначение ig-Theta (Θ) обеспечивает асимптотическую верхнюю и нижнюю границы скорости роста времени выполнения алгоритма. Чтобы вычислить нотацию функции в формате big-Theta, вам нужно найти две неотрицательные функции, f(n) и g(n), такие, что:

Существуют положительные константы c1, c2 и n0 такие, что 0 <= c1 * g(n) <= f(n) <= c2 * g(n) для всех n >= n0.f(n) и g(n) имеют одинаковую асимптотическую скорость роста. Тогда обозначение big-Theta для функции f(n) записывается как Θ(g(n)). Цель этого обозначения — дать грубую оценку времени работы, игнорируя члены более низкого порядка и постоянные коэффициенты.

Например, рассмотрим функцию f(n) = 2n^2 + 3n + 1. Чтобы вычислить ее нотацию в формате big-Theta, мы можем выбрать g(n) = n^2. Затем мы можем найти c1 и c2 такие, что 0 <= c1 * n^2 <= 2n^2 + 3n + 1 <= c2 * n^2 для всех n >= n0. Например, c1 = 1/2 и c2 = 2. Итак, f(n) = Θ(n^2).