алгоритм анализа - порядок роста вопроса

Question

Я изучаю ордера роста "big oh", "big omega" и "big theta". Поскольку я не могу набрать маленькие символы для них, я буду обозначать их следующим образом:

ЗАКАЗ = большой ой
ОМЕГА = большая омега
ТЭТА = большая тета

Например, я скажу n = ORDER (n ^ 2), чтобы обозначить, что функция n имеет порядок n ^ 2 (n растет максимально быстро n ^ 2).

Хорошо, по большей части я понимаю это:

n = ORDER(n^2)             //n grows at most as fast as n^2
n^2 = OMEGA(n)             //n^2 grows atleast as fast as n
8n^2 + 1000 = THETA(n^2)   //same order of growth

Хорошо, вот пример, который меня смущает:

что такое n (n + 1) против n ^ 2

Я понимаю, что n (n + 1) = n ^ 2 + n; Я бы сказал, что он имеет тот же порядок роста, что и n ^ 2; поэтому я бы сказал

n (n + 1) = ТЕТА (n ^ 2)

но мой вопрос, было бы также правильно сказать:

n (n + 1) = ЗАКАЗ (n ^ 2)

пожалуйста, помогите, потому что это сбивает меня с толку. спасибо.

Спасибо, ребята !!

просто чтобы убедиться, что я правильно понимаю, все ли это правда:

n ^ 2 + n = ЗАКАЗ (2000n ^ 2)
n ^ 2 + n = THETA (2000n ^ 2)
n ^ 2 + n = OMEGA (2000n ^ 2)

2000n ^ 2 = ЗАКАЗ (n ^ 2 + n)
2000n ^ 2 = THETA (n ^ 2 + n)
2000n ^ 2 = OMEGA (n ^ 2 + n)

Так что, если f = THETA (g), то f = ORDER (g) и f = OMEGA (g) также верны.

Answer 1

Да, n (n + 1) = Порядок (n ^ 2) правильный.

Если f = Theta (g), то f = Порядок (g) и g = Порядок (f) верны.

Answer 2

Морон верен , и это самый простой способ думать об этом.

Но чтобы понять это, вернитесь к определению для f (n) = O (g (n)): существуют положительные M и n0 такие, что для всех n> n0, f n) <= Mg (n). </p>

Предположим, М = 2. Можете ли вы найти значение n0, такое что для всех n> n0, n ^ 2 + n <= M (n ^ 2)? </p>

(Нарисуйте обе функции ручкой и бумагой, чтобы понять, как они растут по отношению друг к другу.)

Answer 3

Вы можете использовать эту простую таблицу, чтобы получить легкое и интуитивное понимание того, что означают эти символы:

Если f (n) и g (n) две функции, то

Growth Rate
if f(n) = Θ(g(n))   then     growth rate of f(n) = growth rate of g(n)

if f(n) = O(g(n))   then     growth rate of f(n) ≤ growth rate of g(n)

if f(n) = Ω(g(n))   then     growth rate of f(n) ≥ growth rate of g(n)

if f(n) = o(g(n))   then     growth rate of f(n) < growth rate of g(n)

if f(n) = ω(g(n))   then     growth rate of f(n) > growth rate of g(n)

Кроме того, порядок всегда записывается в терминах наивысшего порядка, т. Е. Если порядок O (n ^ 2 + n + 1), то мы просто записываем его как O (n ^ 2), так как n ^ 2 соответствует высший заказ.