В CLRS (Введение в алгоритмы Cormen, Leiserson, Rivest и Stein) для функции
f (n) = an 2 + bn + c
они сказали
Предположим, что мы берем константы c 1= a/4, c 2= 7 a/4, а n 0= 2 · max (| b |/a, √ (| c |/a)).
Тогда 0 ≤ c 1 n 2 ≤ a 2 + bn + c ≤ c 2 n 2 для всех n ≥ n 0.
Поэтому f (n) является Θ (n 2).
Но они не указали, как появились значения этих констант?
Я пытался это доказать, но не мог.
Скажите, пожалуйста, как пришли эти константы?
Нет ничего особенного в этих конкретных константах (кроме того, что в контексте некоторого значения 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 всюду и неравенство выполняется для всех п). Я должен указать, что это правильное решение, хотя мы сделаем немного больше работы, пока не придем к представлению книги.
Мы можем разбить наш анализ на 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.
Идея состоит в том, чтобы (при достаточно большом n) "захватить" интересующую функцию между двумя "чистыми" функциями роста (имеющими только одну константу пропорциональности). На этом рисунке две квадратичные функции (выделенные красным и синим) попадают в ловушку между двумя чистыми функциями роста (черными), а в каждом случае указывается минимально возможное значение n 0.
Итак, как только вы выбрали значения c 1 и c 2, вы можете найти значение n 0, пересекая ваши функции с двумя чистыми функциями роста и пересечением самой правой точки.
Но вы не заботитесь о получении наименьшего возможного значения для n 0 - здесь мы делаем асимптотику, поэтому любое достаточно большое значение будет делать - так что вы можете использовать приближения, чтобы получить верхнюю связанный с ним.
См. ответ davin о том, как получить верхнюю границу для n 0 в форму, указанную в CLRS.
c1 и c2 можно выбрать произвольно, пока 0 < c1 < a и a < c2 < infinity.
n0 вычисляется из этого, так что для всех n>=n0 выполняется неравенство 0 <= c1*n^2 <= an^2 + bn + c <= c2*n^2.
Чтобы доказать, что любой многочлен f (n) = a0 + a1 * n + a2 * n ^ 2 + a3 * n ^ 3 +... + am * n ^ m равен theta (n ^ m), следуйте двум простые шаги. шаг 1. показывают, что f (n) является большим Oh (n ^ m) шаг 2. показывают, что f (n) является большим Омега (n ^ m)
Если оба вышеуказанных условия сохраняются хорошо, то определенно f (n) велико. Theta (n ^ m).
Это обобщение. Полагая m = 2, вы получаете f (n) bigTheta (n ^ 2) Простой.. не так ли?
хорошо его легко 1.c1 <= a + b/n + c/n ^ 2 Теперь здесь a > 0, а b, c - либо положительные, либо отрицательные Теперь мы должны выбрать значение n такое, что b/n + c/n ^ 2 никогда не превосходит a в RHS вышеизложенного, потому что иначе оно станет отрицательным, и так будет c1. но по определению c1 является положительной константой
Итак, мы хотим убедиться a > б/п + с/п ^ 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 = a-a/2-a/4 = a/4 c2 = a + a/2 + a/4 = 7a/4
Это понятие можно распространить на любые значения для любого многочлена.
ура!!!
P (n) = an 2 + bn + c = an 2 (1 + b/(an) + c/(an 2)) = an 2 (1 ± (| b |/a)/n ± (√ (| c |/a)/n) 2
поэтому, если взять, например, q = max (| b |/a, √ (| c |/a)), чем
P (n) ≤ an 2 (1 + (q/n) + (q/n) 2) и если мы возьмем n 0= q, мы получим вторую константу
c 2= 3a аналогично для нижней границы