2015-12-20 22 views
1

Я прошел через основы Big-O обозначение.верхняя граница пересекается без необходимости

F (п) = Ω (г (п)) означает, что CG (п) представляет собой нижнюю границу F (п) такое, что F (п) всегда ≥ CG (п)

е (п) = о (г (п)) означает, что CG (п) является верхней границей на г (п) такое, что F (п) всегда ≤ CG (п) для всех п ≥ n0

enter image description here

верхняя и нижняя граница ясно на графике выше, , но почему это f (n) и upperboun d пересекающихся? когда его четкое определение выше? У этого есть смысл, или я просто указываю без необходимости?

Источник: Руководство Алгоритм Построения Дизайн Skiena

+0

Поведение f (n) в этом контексте является асимптотическим, то есть оно истинно «при достаточно большом n» (как указано в заголовке фигуры, которую вы положили) –

+1

утверждение выполняется для всех n> n0 (как показано в ваша цифра) –

ответ

2

На основе первых двух определений, не должно быть пересечение из-за слова всегда

ф (п) = Ω (g (n)) означает, что cg (n) является нижней границей на f (n) такой, что f (n) равно всегда ≥ cg (n)

f (n) = O (g (n)) означает, что cg (n) является верхней границей на f (n) такой, что f (n)всегда ≤ c.g (п)

Эти определения не совсем правильно. Потому что идея нотации Big-O состоит в проверке количества операций, когда n действительно большой. В условиях неспециалиста это означает, что вы начинаете проверять сложность только после некоторого числа, которое вы считаете достаточно большим. Это указано на вашей картинке:

Верхние и нижние границы допустимых для п> п0 ...

и вот почему на картинке у вас есть вертикальная линия n0. Поэтому вам ничего не стоит перед этой строкой, потому что вы считаете только числа после n0 достаточно большими.

Чтобы сделать эти определения точными, просто добавьте для n> n0 в конце обоих из них.

+0

так, как правило, выделяется здесь на n> n0? Потому что нас интересует масштаб? – brykneval

+1

@brykneval Я бы не сказал, что вам нужно выделить 'n> n0', потому что первая часть важнее. Но вы должны помнить, что когда вы говорите о большом О, вас беспокоят очень большие цифры, поэтому вам не нужны некоторые элементы перед большими числами. Именно поэтому важна роль 'n> n0'. –

+0

, поэтому мое общее предположение было тем, кто был выше меня, всегда будет выше, будь он измеряется в дюймах, или см или метре. но я понял, что он имеет значение только для n> n0, coz есть константа, которая может быть также 0,1 слишком – brykneval

2

Определение просто неточно. Обозначение Big-O относится к асимптотическому росту. Таким образом, его свойства считаются «достаточно большими» N », что означает, что он может не испортиться для небольших N.

В диаграмме, A «достаточно N большой» отмечен как N0, после чего предельное свойство поддерживается.

0

В дополнение к тому, что уже было сказано в других ответах, неравенства в определении неверны, а они должны быть отменены:

е (п) = Q ((п) г) средства с.g (n) - нижняя граница на f (n) такая, что f (n) всегда ≥ cg (n)

f (n) = O (g (n)) означает, что cg (n) является верхней ограничение на е (п), что е (п) всегда ≤ CG (п)

+0

спасибо за указание :-) – brykneval

0

Мое общее предположение здесь было, когда е (п) ≥ G (п), что подразумевает высокий человек всегда высокий несмотря на измерения в дюймах или метр или сантиметр, что верно, но это условие кажется, справедливо только при п> п0

т.е. условие F (N) ≥ CG (п) справедливо только при п> п0

поэтому перед п> п0 мы в принципе не волнует, какое значение они участок сог, то определение не применяется.

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