Что такое простой способ к нахождению C и N при доказательстве Большого Об из Алгоритма?
Передайте его по каналу непосредственно к другому экземпляру, для предотвращения диска наверху. Не беспокойтесь --compress, если Вы не работаете на основе медленной сети, с тех пор на быстрой LAN или обратной петле, сеть наверху не имеет значения.
5 ответов
Вы можете выбрать константу c, добавив коэффициенты каждого члена вашего многочлена. С
| n 5 + 5n 4 + 0n 3 + 10n 2 + 5n 1 + 1n 0 | <= | n 5 + 5n 5 + 0n 5 + 10n 5 + 5n 5 + 1n 5 |
, и вы можете упростить обе стороны, чтобы получить
| n 5 + 5n 4 + 10n 2 + 5n + 1 | <= | 22n 5 |
Итак, c = 22, и это всегда будет верно для любого n> = 1.
It '
Обычно доказательство проводится без выбора конкретного C и №. Вместо доказательства f (n) Например, чтобы доказать, что n 3 + n равно O (n 3 ), выполните следующие действия: (n 3 + n ) / n 3 = 1 + (n / n 3 ) = 1 + (1 / n 2 ) <2 для любого n> = 1. Здесь вы можете выбрать любой C> = 2 с No = 1.
Вы можете проверить, что такое lim abs (f (n) / g (n)), когда n -> + infitity, и это даст вам константу (g (n) is n ^ 5 в вашем примере, f (n) равно (n + 1) ^ 5).
Обратите внимание, что значение Big-O для x -> + infinity состоит в том, что если f (x) = O (g (x) ), то f (x) «растет не быстрее, чем g (x)», поэтому вам просто нужно доказать, что lim abs (f (x) / g (x)) существует и меньше + бесконечности.
Это будет сильно зависеть от функции, которую вы рассматриваете. Однако для данного класса функций вы можете придумать алгоритм.
Например, полиномы: если вы установите C равным любому значению, большему, чем старший коэффициент полинома, вы можете найти N 0 .
После того, как вы разберетесь в волшебстве, вы также должны получить, что большой O - это нотация . Это означает, что вам не нужно искать эти коэффициенты в каждой решаемой вами задаче , если вы убедитесь, что понимаете, что происходит за этими буквами. Вы должны просто оперировать символами в соответствии с нотацией , , в соответствии с ее правилами.
Нет простого общего правила для определения фактических значений N и c. Вы должны вспомнить свои математические знания, чтобы решить эту проблему.
Определение большого O перепутано с определением предела . Это заставляет c удовлетворять:
c> lim | f (n) / g (n) |, если n стремится к + бесконечности.
Если последовательность ограничена сверху, она всегда имеет предел. Если это не так, тогда f не O (g). После того, как вы выбрали бетон c,