В CLRS (Introduction to Algorithms Cormen, Leiserson, Rivest и Stein) для функция
f(n) = an2 + bn + c< /эм>
Они сказали
Предположим, мы берем константы c1 = a/4, c2 = 7a/4 и n0 = 2·max(|b|/a< /em>, √(|c|/a)).
Тогда 0 ≤ c1 n2 ≤ an2 + bn + c ≤ c2n2 для всех n ≥ n< /em>0.
Следовательно, f(n) равно Θ(n2< /над>).
Но они не указали, как появились значения этих констант?
Я пытался это доказать, но не смог.
Скажите, пожалуйста, как пришли эти константы?
В этих конкретных константах нет ничего особенного (кроме того факта, что в контексте определенного значения 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.
Идея состоит в том, чтобы (для достаточно больших n) "поймать" интересующую функцию между двумя "чистыми" функциями роста (которые имеют только одну константу пропорциональности). На этом рисунке две квадратичные функции (нарисованы красным и синим) заключены между двумя чистыми функциями роста (нарисованы черным), и минимально возможное значение n0 в каждой указан случай.
Итак, выбрав значения c1 и c2, вы можете найти значение < em>n0, пересекая вашу функцию с двумя функциями чистого роста и выбирая самое правое пересечение.
Но вас не волнует получение наименьшего возможного значения для n0 — здесь мы используем асимптотику, поэтому любое достаточно большое значение будет do — так что вы можете использовать приближения, чтобы получить верхнюю границу.
См. ответ Давина о том, как получить верхнюю границу для n0 в форме, заданной в CLRS.
1 - 1/4 = 3/4 != 15. Похоже, вы случайно возвели в квадрат a/4.
- person davin; 14.07.2011
c1 и c2 можно выбирать произвольно, пока 0 < c1 < a и a < c2 < infinity. Затем из этого вычисляется n0, так что неравенство 0 <= c1*n^2 <= an^2 + bn + c <= c2*n^2 выполняется для всех n>=n0.
Чтобы доказать, что любой полином 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) is bigTheta(n^2) Simple.. не так ли?
ну, это просто 1.c1‹=a + b/n + c/n^2 Теперь здесь a > 0, а b,c либо положительны, либо отрицательны. Теперь мы должны выбрать значение n так, чтобы b/n + c/n ^2 никогда не превышает a в правой части приведенного выше уравнения, иначе оно станет отрицательным, как и 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=a-a/2-a/4= a/4 c2=a+a/2+a/4= 7a/4
Эту концепцию можно распространить на любые значения любого многочлена.
ваше здоровье!!!
P(n) = an2 + bn + c = an2( 1 + b / ( an ) + c / ( an2 )) = an2( 1 ± ( | b | / a ) / n ± ( √( | c | / a ) / n )2
поэтому, если мы возьмем, например, q = max( | b | / a, √( | c | / a )), чем
P(n) ≤ an< sup>2( 1 + ( q / n ) + ( q / n )2 ) и если мы возьмем n0 = q, то получим вторую константу
c2 = 3a аналогично для нижней границы
