Алгоритм анализа (Big O и Big Omega)

Question

Я неправильно понял этот вопрос на экзамене: назовите функцию, которая не является ни O (n), ни Omega(n).

После попытки самостоятельно изучить этот материал через YouTube, я думаю, что это может быть правильный ответ:

(n³ (1 + sin n)) не является ни O (n), ни Omega(n).

Это было бы точно?

Answer 1

Назовите функцию, которая не является ни O(n), ни Omega(n)

поговорка f ∈ O(g) означает частное

f(x)/g(x)

ограничен сверху для всех достаточно больших x,

f ∈ Ω(g) с другой стороны, означает частное

f(x)/g(x)

ограничен снизу от нуля для всех достаточно больших x,

Таким образом, чтобы найти функцию, которая ни O(n) ни Ω(n) значит найти функцию f такой, что частное

f(x)/x

становится произвольно большим и произвольно близким к нулю на каждом интервале [y, ∞),

Я думаю, что это может быть правильный ответ: (n^3 (1 + sin n)) не является ни O (N), ни Omega (N).

Давайте подключим это в нашем частном:

(n^3*(1 + sin n))/n = n^2*(1 + sin n)

n^2 растет до бесконечности, и фактор 1 + sin n больше 1 примерно для трех из каждых шести n, Так что каждый интервал [y, ∞) коэффициент становится сколь угодно большим. Учитывая произвольный K > 0, позволять N_0 = y + K + 1 а также N_1 самый маленький из N_0 + i, i = 0, 1, ..., 4 такой, что sin (N_0+i) > 0, затем f(N_1)/N_1 > (y + K + 1)² > K² + K > K,

Для Ω(n) отчасти это не так легко доказать, хотя я считаю, что это устраивает.

Но мы можем немного изменить функцию, сохранив идею умножения растущей функции на осциллирующую так, чтобы доказательство стало простым.

Вместо sin n, давайте выберем cos (π*n)и, чтобы сместить нули, добавьте к нему быстро убывающую функцию.

f'(n) = n^3*(1 + cos (π*n) + 1/n^4)

сейчас,

         / n^3*(2 + 1/n^4), if n is even
f'(n) = <
         \  1/n           , if n is odd

и очевидно, что f' не ограничен ни сверху, ни снизу никаким положительным постоянным, кратным n,

Answer 2

Я хотел бы рассмотреть что-то вроде бинарного поиска. Это O(log N) и Ω(log N). Поскольку Омега определяется как нижняя граница, ей не разрешается превышать саму функцию - поэтому O(log N) определенно не является Ω(N).

Я думаю, что некоторые комментарии к удаленному ответу заслуживают некоторого... разъяснения - возможно, даже прямого исправления. Цитируя из CLRS, "Ω-нотация дает нижнюю границу для функции с точностью до постоянного множителя".

Поскольку N² отличается от N более чем на постоянный коэффициент, N² не является Ω(N).