Доказательство и опровержение BigO - PullRequest
Новая
       14

Доказательство и опровержение BigO

8 голосов
/ 12 февраля 2010

При доказательстве и опровержении вопросов Большого О, в которых прямо говорится, используйте определение, чтобы доказать и опровергнуть, мой вопрос: правильно ли я делаю?

Например, у вас есть вопрос, который g (n) = O (f (n)) ... Чтобы доказать это, я делал следующее 

g(n) <= C(F(n))
g(n)/F(n) <= C .. then give n=1 and solve for C , which proves it.

Противоречие, с которым я сталкиваюсь, когда делаю это, когда я подхожу к вопросу опровержения этого материала

например

g (n) = O (F (n)), чтобы опровергнуть это, я бы сделал

g (n)> = C (F (n)) и снова решите для C. Однако это заставляет меня верить, что большой О может быть доказан и опровергнут одновременно? что на 100% неправильно.

Использование чисел реального мира (Доказательство) 

n^2 + 3 = O(n^2)
(n^2 + 3)/n^2  <= C  assume n = 1 then C >= 3

Disproving

n^2 + 3 = O(n^2)


(n^2 + 3)/n^2  >= C  assume n = 1 then C <= 3

n^2 + 3 = O(n^2)

оба они говорят, что при @ n = 1 и c = 3 алгоритм равен O (n ^ 2), а НЕ O (n ^ 2).

Может ли кто-нибудь помочь мне прояснить мою путаницу и помочь мне научиться хорошему алгоритмическому способу решения больших O вопросов?

1 Ответ

11 голосов
/ 12 февраля 2010

Ни одна из ваших техник не работает. Давайте начнем с определения big-O:

f есть O (g), если существуют такие C, N, что | f (x) | & Ле; C | g (x) | для всех x & ge; N

Чтобы доказать, что операторы типа "существуют", вам нужно показать, что все вещи существуют. В случае больших доказательств вы обычно находите вещи, хотя доказательства существования обычно не должны быть конструктивными . Чтобы создать доказательство утверждения «для всех», представьте, что кто-то только что вручил вам конкретные значения. Будьте осторожны, вы не делаете неявных предположений об их свойствах (вы можете явно указывать свойства, такие как N> 0).

В случае доказательства big-O вам нужно найти C и N . Показано | г (н) | ≤ C | F (n) | для одного n не достаточно.

Например, «n 2 + 3 - это O (n 2 )»: 

 For n &ge; 2, we have: 
    n<sup>2</sup> &ge; 4 > 3
      &rArr; n<sup>2</sup>-1 > 2
      &rArr; 2(n<sup>2</sup>-1) > (n<sup>2</sup>-1)+2
      &rArr; 2n<sup>2</sup> > (n<sup>2</sup>-1)+4 = n<sup>2</sup>+3
 Thus n<sup>2</sup>+3 is O(n<sup>2</sup>) for C=2, N=2.

Чтобы опровергнуть, вы принимаете отрицание утверждения: покажите, что нет C или N . Другими словами, покажите, что для всех C и N существует такое n> N, что | f (n) | > C | g (n) |. В этом случае C и N квалифицированы «для всех», поэтому притворитесь, что они вам даны. Поскольку n квалифицируется как "существует", вы должны его найти. Здесь вы начинаете с уравнения, которое вы хотите доказать, и работаете в обратном направлении, пока не найдете подходящий n .

Предположим, мы хотим доказать, что n не является O (ln n). Представьте, что нам даны N и C, и нам нужно найти n & ge; N такой, что n> C ln n. 

For all whole numbers C, N, let M=1+max(N, C) and n = e<sup>M</sup>. Note n > N > 0 and M > 0.
Thus n = e<sup>M</sup> > M<sup>2</sup> = M ln e<sup>M</sup> = M ln n > C ln n. QED.

Доказательства x> 0 & rArr; e x > x 2 и "n не O" (ln n) "& rArr; «n - это не O (log b n)», оставленные в качестве упражнений.

...