Что такое Big-O этого алгоритма из двух частей?

Question

Учитывая следующий алгоритм для набора данных размером N:

1. Разделите данные на блоки M = (N / lg N) за O (N) времени.
2. Разделить блоки по времени O (M lg M).*

Что такое биг-о?Как мне оценить (N / LG N) * LG (N / LG N)?

Если это не O (N), то достаточно ли М, чтобы все стало О (N)?

* Алгоритм разбиения - это STL stable_partition, который в этом примере будет выполнять M тестов и не более M lg M перестановок. Но , объекты, подлежащие обмену, представляют собой блоки размером lg N. Относит ли это практическое время шага 2 обратно к O (N lg N), если их необходимо поменять местами?

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

Answer 1

Вы оцениваете, делая немного математики.

log(x/y) = log(x) - log(y)
->
log(N / log(N)) = log(N) - log(log(N))

Итак, подключите это обратно и объедините в одну дробь.
N(log(N) - log(log(N))) / log(N)
=
N - N(log(log(N)) / log(N))
<=, поскольку log (log (N)) <= log (N) как N -> инф., Это похоже на умножение на <= 1 <BR>N

Итак, все это O (N).

Вы можете легко догадаться, что это O (N log N), заметив, что M = N / log N само по себе O (N).Я не знаю быстрого способа выяснить, что это O (N) без малейших сомнений с моей стороны из-за необходимости умножения на log M.

Answer 2

Это O (N):

N / lgN * lg(N / lgN)=N / lgN * (lgN-lglgN)=N*(1-lglgN / lgN)<=N