Для каждой функции F (п) и времени Т, определения наибольшего размера п проблема, которая может быть решена за время т,найти значение п из уравнения, NlogN = Т
где Р (п) = t сек.
Для приведенного выше вопроса, я должен решить для F (п) = NlogN , что означает NlogN = Т
как узнать значение п, из приведенного выше уравнения ..?
Если это вопрос программирования, я бы разрешил его с помощью бинарного поиска на n от 1 to t (как низкий, так и высокий в начале). Если n * log (n) на mid превышает t, принесите high в mid еще low в mid и альта.
И если это вопрос математики, я бы посоветовал вам разместить его в сообществе mathematics.stackexchange.
двоичный поиск можно использовать только в том случае, если 'f (n)' является монотонным, поскольку OP не предоставляет никакой информации об этом. Лучшим выбором будет аппроксимация, поиск чего-то подобного [см. Примерный класс в C++] (http://stackoverflow.com/q/29166819/2521214) с достаточно небольшим начальным шагом – Spektre
@Spektre, Почему вы так говорите? Разве 'n log n' не является монотонной функцией? – vish4071
'f (n)' is 'n * log (n)' для 'n', но является' y = f (x) 'монотонным? Я не знаю, поскольку я не знаю, что стоит за «f (x)», и поэтому вы не можете предположить, что это ... – Spektre
Это не сайт HW. Специально не математика HW ... –
Вам нужна функция [Lambert W] (https://en.wikipedia.org/wiki/Lambert_W_function), известная как «журнал продуктов». –
Я делаю упражнения из своей книги, это не HW. Я просто хочу узнать, как решить эти уравнения. – Igniter