Решение проблемы Big O Log - PullRequest
1 голос
/ 28 июля 2010

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

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

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

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

Заранее спасибо!

Ответы [ 3 ]

3 голосов
/ 28 июля 2010

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

1 голос
/ 28 июля 2010

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

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

Извините, это всего лишь разновидность "грубой силы с Excel": -)

Edit:

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

1 голос
/ 28 июля 2010

Лучше всего использовать метод Ньютона.

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

...