Проблема с пониманием постоянной части Big O

Может ли кто-нибудь объяснить мне цель постоянной части большой записи O?Проблема с пониманием постоянной части Big O

Я попытаюсь объяснить, где я нахожусь сейчас в плане понимания:

В основном у вас есть функция, например f(x) = x^2 + 1 и g(x) = x^3

Итак, f(x) является O(g(x)), потому что для некоторого значение x, k, за каждые x > k, f(x) <= **C**|g(x)|.

Для этого уравнения, k = 2.

Возможно, я уже ошибаюсь, поэтому, пожалуйста, исправьте меня, если да.

Это кажется достаточно интуитивно понятным, но я немного смущен о постоянном значении, C.

источник

2012-04-30 Joe Neidermeier

Это должно быть на [http://math.stackexchange.com/](http://math.stackexchange.com/). Поскольку [Stack Overflow предназначен для профессиональных и энтузиастов-программистов, людей, которые пишут код, потому что им это нравится. Мы чувствуем, что у лучших вопросов переполнения стека есть немного ** исходного кода ** в них] (http://stackoverflow.com/faq#questions) –

O нотация - это форма функции, а не ее абсолютная величина. Добавление или умножение на константу не меняет форму. –

Итак, подождите, если вы измените константу, например, если вы ее увеличите, то вы можете просто увеличить значение k тоже, и поэтому функция все равно будет O (другая функция)? это то, как это работает? –

Это просто константа. Чтобы доказать, что f (x) есть O (g (x)), вы должны выбрать некоторые конкретные константы C и k и доказать, что они удовлетворяют этому условию. Что за смущает?

источник

2012-04-30 07:24:07

Итак, подождите, если вы измените константу, например, если вы увеличите ее, то вы можете просто увеличить значение k, и поэтому функция будет по-прежнему равна O (другая функция)? –

- это то, как это работает? –

Увеличение k ничего не изменит, потому что вас интересует, что происходит со значениями x между k и бесконечностью. Но вы не выбираете k, вы показываете, что такой k существует вообще. Нет никаких ВОЗМОЖНЫХ значений c и k, которые показывают, что g (x) есть O (f (x)). – philosodad

В следующей строке плохо сформулированы:

F (X) = О (г (х)), так как при некотором значении х, к, для каждого х> к, Р (х) < = C | g (x) |

Ниже приводится более точным:

F (X) = О (г (х)), так как существует значение к и значение С такими , что при любом значении х Большого чем k: f (x) < = C | g (x) |.

Надеюсь, это поможет.

источник

2012-04-30 22:43:15 cdiggins

Проблема с пониманием постоянной части Big O

ответ

Смежные вопросы