Дайте две функции f (n) и g (n) такие, что f (n) не является O (g (n)) и g (n) не O (f (n)).Big O для 2 функций, не принадлежащих друг другу
Когда я начал об этом думать, я подумал о n и n^2. Но, читая больше, я понял, что если моя функция f есть n и g есть n^2, то f primary принадлежит O (g (n)). Итак, я вернулся на круги своя. Любые выводы о том, как это сделать?
Подсказка: ваши функции должны быть довольно извращенными. Попробуйте использовать sin (n).
Также рассмотрите возможность построения f и g чрезвычайно вручную. Выделите несколько интервалов, таких как [1,2], [3,4], [5,6], ... где f много больше g и пусть g намного больше f на других интервалах.
Пусть f (n) = n% 2, g (n) = 1-n% 2. (Здесь x% y такой же, как в C - остаток x после деления на y).
Ни f = O (g), ни g = O (f). Для нечетного n существует k> 0 такое, что f (n) < = kg (n), так как g (нечетное) = 0 и f (нечетное) = 1. Аналогично, для четного n не существует k> 0 такое, что g (n) < = kf (n).
Первое, что приходит мне на ум.
f(n) = (-n)^n
g(n) = 2*n
Лучше спросить на https://cs.stackexchange.com/ – Nayuki
Это точная копия. У кого-то уже была эта задача в университете – xenteros