Я бы разбил это на несколько простых, многократно используемых лемм:
Лемма 1: Для положительной постоянной k, f = O (g) тогда и только тогда, когда f = O (кг).
Доказательство. Предположим, что f = O (g).Тогда существуют такие постоянные c и N, что | f (n) | N. Таким образом, | f (n) |<(c / k) (k | g (n) |) для n> N и постоянной (c / k), поэтому f = O (кг).Обратное утверждение тривиально аналогично.
Лемма 2: Если h - положительная монотонно возрастающая функция, а f и g положительны для достаточно большого n, то f = O (g) тогда и только тогда, когда h (f) = O (h (g)).
Доказательство. Предположим, что f = O (g).Тогда существуют такие постоянные c и N, что | f (n) | N. Так как f и g положительны для n> M, f (n) max (N, M).Поскольку h монотонно возрастает, h (f (n)) max (N, M) и, наконец, | h (f (n)) | max (N, M), поскольку h положительно.Таким образом, h (f) = O (h (g)).Обратное следует аналогично;ключевой факт заключается в том, что если h монотонно возрастает, то h (a) a Лемма 3: если h - обратимая монотонно возрастающая функция, то f= O (g) тогда и только тогда, когда f (h) + O (g (h)).
Доказательство. Предположим, что f = O (g).Тогда существуют такие постоянные c, N, что | f (n) | N. Таким образом, | f (h (n)) | N. Поскольку h (n) обратимо и монотонно возрастает, h (n)> N всякий раз, когда n> h ^ -1 (N).Таким образом, h ^ -1 (N) - новая необходимая нам константа, а f (h (n)) = O (g (h (n)). Обратное следует аналогичным образом, используя обратную формула g.
Лемма 4: Если h (n) отлично от нуля при n> M, то f = O (g) тогда и только тогда, когда f (n) h (n) = O (g (n) h (n)).
Доказательство: если f = O (g), то для констант c, N, | f (n) | N. Поскольку | h (n) | положительно дляn> M, | f (n) h (n) | max (N, M) и, следовательно, f (n) h (n) = O (g (n) h (n)). Обратное аналогично следует с использованием 1 / h (n).
Лемма 5a: log n = O (n).
Доказательство: Пустьf = log n, g = n. Тогда f '= 1 / n и g' = 1, поэтому при n> 1 g увеличивается быстрее, чем f. Более того, g (1) = 1> 0 = f (1),поэтому | f (n) | <| g (n) | для n> 1 и f = O (g).
Лемма 5b: n! = O (log n).
Доказательство: предположим, что в противном случае противоречие, и пусть f = n и g = log n. Тогда для некоторых констант c, N, | n | N.
Пусть d = max(2, 2c, sqrt (N + 1)). По расчету из леммы 5a, так как d> 2> 1, log d 2d (log d)> = d log d + d log 2 = d (log 2d)> 2c log 2d> c log (2d ^ 2) = cg (2d ^ 2) = c | g (2d ^2) |для 2d ^ 2> N противоречие.Таким образом, f! = O (g).
Итак, теперь мы можем собрать ответ на первоначально заданный вами вопрос.
Шаг 1:
log n = O(n^a)
n^a != O(log n)
Для любой положительной константы a.
Доказательство: log n = O (n) по лемме 5a.Таким образом, log n = 1 / a log n ^ a = O (1 / an ^ a) = O (n ^ a) по леммам 3 (для h (n) = n ^ a), 4 и 1. Второй фактследует аналогично, используя лемму 5b.
Шаг 2:
log^5 n = O(n^0.01)
n^0.01 != O(log^5 n)
Доказательство: log n = O (n ^ 0,002) к шагу 1. Затем по лемме 2 (с h (n)= n ^ 5), log ^ 5 n = O ((n ^ 0,002) ^ 5) = O (n ^ 0,01).Второй факт следует аналогично.
Окончательный ответ:
n log^5 n = O(n^1.01)
n^1.01 != O(n log^5 n)
Другими словами,
f = O(g)
f != 0(g)
f != Omega(g)
Доказательство: примените лемму 4 (используя h (n) = n) к шагу 2.
С практикой эти правила становятся «очевидными» и приобретают вторую природу.и если ваш тест не требует, чтобы вы доказали свой ответ, вы обнаружите, что решаете проблемы такого рода.