Решение проблемы большого журнала O

Question

У меня вопрос, который исходит из книги алгоритмов, которую я читаю, и я в тупике о том, как ее решить (прошло много времени с тех пор, как я выполнил математику в журнале или экспоненте). Проблема заключается в следующем:

Предположим, что мы сравниваем реализации сортировки вставки и сортировки слияния на той же машине . Для входов размера n входы сортировки сортируются в 8n^2 шагах, а сортировка слияния выполняется в 64n log n шагов. Для каких значений n делает сортировку сортировки сортировки сортировки?

Журнал является базой 2. Я начал пытаться решить для равенства, но застрял вокруг n = 8 log n.

Я хотел бы ответить, чтобы обсудить, как решить эту задачу математически (грубая сила с преимуществом недопустимо извините;)). Любые ссылки на описание журнала math были бы очень полезны в моем понимании вашего ответа.

Спасибо заранее!

Answer 1

http://www.wolframalpha.com/input/?i=solve%288+log%282%2Cn%29%3Dn%2Cn%29 (отредактирован, поскольку старая ссылка перестала работать)

Answer 2

Ваш лучший выбор - использовать метод Ньютона.

http://en.wikipedia.org/wiki/Newton%27s_method

Answer 3

Одним из способов решения этого было бы просто взять калькулятор графиков и график обе функции (см ссылку Wolfram в другой ответ). Найдите интересующее вас пересечение (если есть несколько пересечений, как есть в вашем примере).

В любом случае не существует простого выражения для решения n = 8 log₂ n (насколько я знаю). Может быть проще перефразировать вопрос так: «Найти нуль f (n) = n - 8 log₂ n". Сначала найдите регион, содержащий интересующее вас пересечение, и продолжайте сокращать этот регион. Например, предположим, что вы знаете, что ваша цель n больше 42, но меньше 44. f (42) меньше 0, а f (44) больше 0. Попробуйте f (43). Это меньше, чем 0, поэтому попробуйте 43.5. Это все равно меньше 0, поэтому попробуйте 43.75. Это больше, чем 0, поэтому попробуйте 43.625. Это больше, чем 0, поэтому продолжайте движение вниз и так далее. Этот метод называется binary search.

К сожалению, это всего лишь разновидность «грубой силы с первенствует» :-)

Edit:

Для удовольствия, я сделал таблицу, которая решает эту проблему с помощью бинарного поиска: binary‑search.xls. Логика двоичного поиска находится во втором столбце данных, и я просто автоматически расширил это.