Если не BigO, то BigOmega?

Question

Итак, если функция или время выполнения не BigO из f (n), можем ли мы сказать, что ее BigOmega равно f (n)?

Answer 1

Нет. Например, функция

        / n^n if 2|n
 f(n) = |
        \ 0   otherwise

не находится ни в O(n), ни в Ω(n): для любых значений N и c всегда будет значение n > N, например, f(n) > c*n (поэтому оно не может быть в O(n)) и другое значение m > N, такое, что f(m) < c*m (поэтому его не может быть в Ω(n)).

Answer 2

Нет, не обязательно.

Как обычно, с такими теоретическими темами вы можете рассмотреть некоторые забавные функции.Давайте возьмем функцию g, которая возвращает значение 1/n для всех нечетных входов, а для четного входа n возвращает n*n.

Эта функция не находится в BigO f (n) =n (тождественная функция).Это должно быть понятно, так как вы получаете n * n результатов.

Однако это также не относится к BigOmega с f (n) = n, потому что для очень больших чисел вам не гарантируется, что g (n)> = k * f (n).

Answer 3

Даже если функции монотонно растут, т. Е. N f (n) \ leq f (m), то по-прежнему неверно, что f (n) \ neq O (g (n) подразумевает f (n) = \ Omega (g (n)).

Рассмотрим, например, f (n) = g (n) ^ 2 для четного n и g (n-1) для нечетного n и g (n) = f (n) ^ 2 для n нечетных и f (n-1) для n четных, с f (0) = 2, g (0) = 2.

Оба монотонно растут, но ниявляется ой-ой другой (очень быстро расти).