Доказательство и опровержение BigO
В доказательстве и опровержении Больших вопросов O, который, поскольку, которые явно говорят, используют определение, чтобы доказать и опровергнуть, мой вопрос, является тем, что я делаю корректный?
Например, у Вас есть вопрос, который является 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 снова. Однако это приводит меня полагать, что большой O может быть доказан и опровергнут сразу? который составляет 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 ответ
Деке - это двойная очередь, которая позволяет легко вставлять/удалять с любого конца. Очереди разрешают только вставку в одном конце и извлечение из другого.
-121--891481-deque поддерживает вставку/выскальзывание с задней стороны и очередь
поддерживает только вставку с задней стороны и выскальзывание с передней стороны. Вы знаете, FIFO (первый в первом выходе).
-121--891482-Ни одна из ваших методик не работает. Начнем с определения big-O:
f - O (g) iff существует C, N так, что | f (x) | ≤ C | g (x) | для всех x ≥ N
Чтобы доказать, что «существуют» операторы типа, вы должны показать, что вещи существуют. В случае больших доказательств, вы обычно находите вещи, хотя доказательства существования, как правило, не должны быть конструктивными . Чтобы построить доказательство для заявления «для всех», сделайте вид, что кто-то просто передал вам конкретные ценности. Будьте осторожны и не делайте неявных предположений об их свойствах (можно явно определить свойства, например, N > 0).
В случае подтверждения большого вывода необходимо найти C и N . Отображение | g (n) | ≤ C 'F (n) | для одного n недостаточно.
Для примера «n 2 + 3 - это O (n 2 )»:
For n ≥ 2, we have:
n2 ≥ 4 > 3
⇒ n2-1 > 2
⇒ 2(n2-1) > (n2-1)+2
⇒ 2n2 > (n2-1)+4 = n2+3
Thus n2+3 is O(n2) 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 ≥ N так, что n > C ln n.
For all whole numbers C, N, let M=1+max(N, C) and n = eM. Note n > N > 0 and M > 0. Thus n = eM > M2 = M ln eM = M ln n > C ln n. QED.
Доказательства x > 0 ⇒ e x > x 2 и «n не является O (ln n)» ⇒ «n не является O (регистрация b n)», оставшимся как упражнения.