Как вычислить 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 является Lambert W function (см особенно "Пример 2"). Было доказано, что W не может быть выражен с помощью элементарных операций.

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

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, больше определенного числа или, наоборот, самый большой набор проблем, который можно решить, используя этот алгоритм и это число операций, меньше определенного числа.

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

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

some help with logs