асимптотическая тесная оценка для квадратичных функций

Question

В CLRS ( Введение в алгоритмы (автор Cormen, Leiserson, Rivest и Stein)) для функции

f ( n ) = и ² + млрд + c

они сказали

Предположим, мы берем константы c ₁ = a / 4, c ₂ = 7 a / 4 и n ₀ = 2 · max (| b | / a , √ (| c | / a )).
Тогда 0 ≤ c ₁ n ² ≤ an ² + bn + c ≤ c ₂ n ² для всех n ≥ n ₀ .
Поэтому f ( n ) равно Θ ( n ² ).

Но они не указаликак пришли значения этих констант?
Я пытался доказать это, но не смог.
Скажите, пожалуйста, как эти константыпришел?

Answer 1

В этих конкретных константах нет ничего особенного (кроме того факта, что в контексте определенного значения n они удовлетворят тэтасе f). Нет магии. Если вы можете найти другие положительные константы, при которых сохраняется отношение, которое так же верно (на самом деле, c1 может быть ka для любого 0<k<1). Хотя, поскольку они там, давайте проанализируем c1:

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

c1*n^2 <= an^2 + bn + c

Давайте возьмем их значение: c1 = a/4. Для чего n мы можем гарантировать выполнение неравенства? Мы могли бы решить:

a/4*n^2 <= an^2 + bn + c
<==> 0 <= 3a/4*n^2 + bn + c

Квадратика имеет решения в (-b +- sqrt(b^2-3ac)) / (3a/2), только положительный из которых представляет какой-либо интерес, поскольку у нас есть полином положительного ведущего коэффициента, поэтому нам требуется n > 2 * (sqrt(b^2-3ac) - b) / 3a, который хорошо определен, предполагая b^2 >= 3ac (а если нет, то квадратика положительно определена, что даже лучше, поскольку ее> = 0 везде и неравенство выполняется для всех n). Я должен отметить, что это правильное решение, хотя мы сделаем немного больше, пока не достигнем представления книги.

Мы можем разделить наш анализ на 2 случая. Для начала давайте предположим, что |b|/a >= sqrt(|c|/a). Таким образом, мы можем связать сверху внутреннюю часть sqrt(...) с 4b^2 и потребовать n > 2/3 * [sqrt(4b^2)-b]/a, который может быть ограничен сверху 2/3 * 3|b|/a = 2|b|/a.

Второй случай, допустим |b|/a < sqrt(|c|/a). Таким образом, мы можем связать сверху внутреннюю часть sqrt(...) с 4a|c| и потребовать n > 2/3 * [sqrt(4a|c|)-b]/a, который может быть ограничен сверху 2/3 * 3*sqrt(a|c|)/a = 2sqrt(|c|/a).

Таким образом, в каждом случае мы видим, что когда мы берем max(|b|/a, sqrt(|c|/a)), наше неравенство выполняется, когда n > 2 * max

Аналогично для c2.

Answer 2

Идея состоит в том, чтобы (для достаточно больших n ) "заманить в ловушку" интересующую функцию между двумя "чистыми" функциями роста (которые имеют только одну константу пропорциональности). На этом рисунке две квадратичные функции (нарисованы красным и синим цветом) заключены между двумя чистыми функциями роста (нарисованы черным цветом), и минимально возможное значение n ₀ в каждом случае равно указано.

Итак, выбрав значения c ₁ и c ₂ , вы можете найти значение n ₀ путем пересечения вашей функции с двумя функциями чистого роста и выбора самого правого пересечения.

Но вас не волнует получение наименьшего возможного значения для n ₀ - здесь мы делаем асимптотику, поэтому любое достаточно большое значение будет сделать - чтобы вы могли использовать аппроксимации для получения верхней границы.

См. Ответ Дэвина о том, как получить верхнюю границу для n ₀ в форме, указанной в CLRS.

Answer 3

P (n) = ² + bn + c = ² (1 + b / (an) + c / (an ² )) = ² (1 ± (| b | / a) / n ± (√ (| c | / a) / n) ²
поэтому, если мы возьмем, например, q = max (| b | / a, √ (| c | / a)) , чем
P (n) ≤ an ² (1 + (q / n) + (q / n) ² ) , и если мы примем n ₀ = q , чем мы 'Получим вторую константу
c ₂ = 3a аналогично для нижней границы

Answer 4

хорошо, это просто 1.c1 <= a + b / n + c / n ^ 2 Теперь здесь a> 0, в то время как b, c либо положительны, либо отрицательны. Теперь мы должны выбрать значение n такое, что b / n +c / n ^ 2 никогда не превышает a в RHS вышеупомянутого уравнения, потому что иначе оно станет отрицательным и c1 тоже.но по определению c1 является положительной константой

Поэтому мы хотим убедиться, что a> b / n + c / n ^ 2

, если мы выберем n = 2 * max (| b | /a, sqrt (| c | / a)) мы получим b / n + c / n ^ 2 как выражение, значение которого меньше, чем a / 2 + a / 4.

, таким образом, a + b /n + c / n ^ 2 будет иметь максимальное значение как a + a / 2 + a / 4 и минимальное значение как a- (a / 2 + a / 4), которое является ничем иным, как значениями c2 и c1.

c1 = aa / 2-a / 4 = a / 4 c2 = a + a / 2 + a / 4 = 7a / 4

Эта концепция может быть распространена на любые значения для любого многочлена ..

ура !!!

Answer 5

Чтобы доказать, что любой многочлен f (n) = a0 + a1 * n + a2 * n ^ 2 + a3 * n ^ 3 + ... + am * n ^ m является тэтой (n ^ m), выполните два простые шаги шаг 1. покажите, что f (n) - это bigOh (n ^ m) шаг 2. показать, что f (n) это bigOmega (n ^ m)

Если оба вышеуказанных условия выполняются, то определенно f (n) - это bigTheta (n ^ m).

Это обобщение. Положив m = 2, вы получите f (n) bigTheta (n ^ 2) Просто .. не так ли?

Answer 6

c1 и c2 могут быть выбраны произвольно, если только 0 < c1 < a и a < c2 < infinity. Затем из этого вычисляется n0, так что неравенство 0 <= c1*n^2 <= an^2 + bn + c <= c2*n^2 выполняется для всех n>=n0.