любая линейная функция an + b есть O (n ^ 2) CLRS

Question

В 3-м издании CLRS, в частности, в разделе 3.1 (стр. 47 в моей книге), они говорят

, когда a> 0, любая линейная функция an + b находится в O (n ^ 2), что легко проверить, взяв c = a + | b | и n0 = max (1, -b / a).

, где n0 - это значение, такое, что когда n> = n0, мы можем показать, что + b <= cn ^ 2 в доказательстве вышеупомянутое. </p>

1. Я пытался проверить это, но я не смог пройти очень далеко :(
2. Как они выбрали эти значения c и n0? Я знаю, что единственное, что Дело в том, что существуют такие c и n0, что вышеприведенное верно для доказательства того, что + b есть O (n ^ 2), но мне интересно, как они выбрали именно эти значения c и n0? не кажется произвольным, как будто они применяли какую-то технику, которую я никогда раньше не видел, чтобы получить их.

Спасибо.

Answer 1

Давайте рассмотрим простой случай, когда a и b оба положительные. Авторы пытаются создать значение, в котором функция quadrati c доминирует в линейной функции при n> = 1. Вот и все. Они просто пытаются создать общее решение, чтобы показать, где правая парабола доминирует над любой линией.

Так что для n=1 значение линейной функции (то есть l(n) = an + b) будет a+b когда n=1. Доминирующий квадратик c без каких-либо линейных подфункций (т.е. q(n) = c * n^2) будет доминировать над линейной функцией, l(n) при n=1, если мы выберем c = a + b. Так, q(n) = (a+b)n^2 доминирует l(n) = an + b, когда n>=1, предполагая, что a и b оба положительны. Вы можете проверить примеры для печати 30x^2 и 10x + 20 на Densmos .

Это немного сложнее, когда b отрицательно, но положительный случай - это, в основном, точка .