Как рассчитать n log n = c

Question

У меня есть проблема с домашним заданием для моего класса алгоритмов, требующая, чтобы я вычислил максимальный размер задачи, которая может быть решена за заданное количество операций, используя алгоритм O (n log n) (то есть: n log n = c) , Я смог получить ответ путем аппроксимации, но есть ли чистый способ получить точный ответ?

Answer 1

Для этого уравнения нет формулы в замкнутой форме.По существу, вы можете преобразовать уравнение:

 n log n = c
log(n^n) = c
     n^n = exp(c)

Затем это уравнение имеет решение вида:

n = exp(W(c))

, где W - Функция Ламберта W (см. особенно «Пример 2»).Было доказано, что W нельзя выразить с помощью элементарных операций.

Однако f(n)=n*log(n) является монотонной функцией.Вы можете просто использовать разделение пополам (здесь, в python):

import math

def nlogn(c):
    lower = 0.0
    upper = 10e10
    while True:
        middle = (lower+upper)/2
        if lower == middle or middle == upper:
            return middle
        if middle*math.log(middle, 2) > c:
            upper = middle
        else:
            lower = middle

Answer 2

обозначение O дает только самый большой член в уравнении. Т.е. производительность вашего алгоритма O (n log n) может быть лучше представлена ​​c = (n log n) + n + 53.

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

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

Обозначение O полезно для сравнения 2 алгоритмов, т. Е. Алгоритм O (n ^ 2) работает быстрее, чем алгоритм O (n ^ 3) и т. Д.

см. Википедия для получения дополнительной информации.

некоторая помощь с журналами