Ну у меня есть два вопроса: -Функции роста алгоритма?
Если е (п) функция, скорость роста можно найти то, для всех трех нотаций будет ли г (п) такой же, как и для F (n) = O (g (n)) и аналогично для омега и тета?
Обозначение Тета - «омега и о», если в некотором случае, если функции oh и omega различны, то как мы найдем там тета-функцию? Благодаря :)
О, Θ и Ω обозначения представляют собой связанные, но совершенно разные понятия. O-нотация выражает асимптотическую верхнюю границу относительно скорости роста функции; он говорит, что функция в конечном счете ограничена сверху некоторым постоянным кратным некоторой другой функции. Ω Обозначение похоже, но дает нижнюю границу. Θ обозначение дает асимптотическую ограниченную границу - при достаточно больших входах алгоритм растет со скоростью, ограниченной и сверху, и снизу константой, кратной функции.
Если F (п) = О (г (п)), это не всегда верно, что Р (п) = Ω (г (п)), или, что Р (п) = Θ (г (п)). Например, 1 = О (п), но 1 ≠ Ω (п), потому что п растет быстрее, чем строго 1.
Если вы обнаружили, что Р (п) = О (г (п)) и Ω (час (n)), где g (n) h (n), вам может потребоваться более точный анализ для определения функции j (n) такой, что f (n) = Θ (j (n)). Если g (n) = Θ (h (n)), то вы можете заключить, что f (n) = Θ (g (n)), но если верхняя и нижняя границы различны, механический способ определения Θ скорость роста функции.
Надеюсь, это поможет!
f (n) = O (g (n)) означает, что n> N => | f (n) | ≤C | g (n) | для некоторых констант N и C.
f (n) = Ω (g (n)) означает, что n> N => | f (n) | ≥C | g (n) | для некоторых констант N и C.
f (n) = Θ (g (n)) означает, что f (n) = O (g (n)) и f (n) = Ω (g (n)) ,
Невозможно, чтобы все f находили ag таким образом, что f (n) = Θ (g (n)), если мы хотим, чтобы g была «хорошей» функцией (например, что-то вроде n^r * Log (n)^s). Например, если f (n) = cos (n) ² * n + sin (n) ² * n², мы имеем f (n) = O (n²) и f (n) = Ω (n), но мы можем ' t найти «хороший» g такой, что f (n) = Θ (g (n)).