Большое О, Тета и Омега

Не уверен правильный ли раздел. Вообщем хочу разобраться с большим О, Омегой и Тетой. Насколько я понял большое О говорит о том, насколько плохо будет работать алгоритм (worst case), Тета насколько хорошо (best case) а Омега чему будет равно время выполнения.
Есть у меня еще задачи, хотелось бы понять как их решать.

Объясните можалуйста как решить хотябы пару примеров

1

Сообщение от Dimitrij1 Насколько я понял большое О говорит о том, насколько плохо будет работать алгоритм (worst case)

В чистом виде O-нотация применяется к функциям и говорит об оценке поведения одной функции при помощи другой.
Применимо к алгоритмам речь в качестве одной из функций берётся, например, зависимость времени в худшем случае от параметра задачи.
O оценивает сверху, но не снизу, в частности, для любой функции
Омега оценивает снизу, в частности, в тех же предположениях.
Тета оценивает с двух сторон.

Сообщение от Dimitrij1 Есть у меня еще задачи, хотелось бы понять как их решать.

Если это задачи, как на картинки, то решать их следует без метафизики и философии, просто подставляя конкретные функции в формулы из определений и проверяя полученные суждения на истинность (доказуемость).

Сообщение от Dimitrij1 Объясните можалуйста как решить хотябы пару примеров

Ну ок.

Пример (a). О
f(n)=n+100
g(n)=n+200

узнаем, верно ли
Для этого смотрим в определение:

Докажем сперва такую лемму: . Действительно, 0 < 100, остальное дело техники. Очевидно.
Заметим, что если c=1, n_0=0, то истинно.
Стало быть,

что и требовалось доказать.

Пример (a) наоборот
докажем
по определению это эквив.

доказываем аналогично, положив с=2, n_0=100. То есть сначала доказываем при n>100, а потом исходное утверждение.

Ещё один пример: (g)
f(n) = sqrt(n)
g(n) = (log(n))^2


Структура доказательства (тут важно обратить внимание на порядок кванторов)
1. эквивалентные преобразования и упрощения, порядок кванторов сохраняется
2. замена
3а. сводим задачу к другой, более известной. конец.
3б. или доказываем своими силами, исследуя кривые
4. находим области, где производная 1-я функции больше второй
5. показываем, что в этой области есть хотя бы одна точка, где 1-я функция равна второй.
6. прямолинейно доказываем исходное утверждение. конец.

Докажем, что
это эквив.

Введём обоз1начение и сделаем замену . Теперь перепишем исходное утверждение с учётом и

(тут я опускаю детали формальных переходов)
Если аккуратно ещё один интуитивно очевидный пересход сделать, сведём задачу к
[latex]m \not\in O(\ln m)[latex]
Теперь будем решать её:

Нарисуем две кривые и посмотрим на производные:
dm/dm = 1, d(a ln(m))/dm = a / m.
Очевидно, 1>a/m при m>a. В частности, это 1>a/m выполняется при m>2a.
Заметим, что 2a > a ln(2a) = a + a ln 2 при любых a, то есть при m=2a неравенство выполняется.
Таким образом, для любого a любое число m > 2a выполняется m > a \ln m. Среди таких m > 2a найдётся число, большее n0^(1/4), в частности, m=max(2a,n0^(1/4))+1.
Далее аккуратно навешиваем кванторы один за одним и получаем

что эквивалентно исходному утверждению.
доказано.

Всё. Вспомнил технику, освежил память.

1