Вопрос про логарифм

[Эйнж]

Читаю книгу "Алгоритмы: построение и анализ", в начальном разделе есть задачка,
"Предположим, на одной и той же машине проводится сравнительный анализ реализации двух алгоритмов сортировки, работающих по методу вставок и методу слияния. Для сортировки n елемнтов методом вставки необходимо 8(n^2) шагов, а методом слияния 64*n*lg(n) шагов. При каком значении n время сортировки методом вставок превысит время сортировки методом слияния?"

Как я понимаю, создаем уравнение:
8(n^2) = 64*n*lg(n)
упрощаем
8n = 64*lg(n)
1/8 = lg(n)/n

вопрос, как дальше ? или ход мыслей не верный.

[Аватар]

Меняя в цикле while или repeat n от 1 и дальше найти то n, когда 8(n^2) станет больше, чем 64*n*lg(n). Можно и решить уравнение 1/8 = lg(n)/n, но енто посложней будет

[ViktorR]

В данном случае ошибка в том, что пишется равенство.
n - целое число.
Если считать, что шаг - размерность времени, то правильнее написать неравенство. При некотором n должно случиться, что:
8(n^2) >= 64*n*lg(n)
8n >= 64*lg(n)

n >= 8*lg(n) - это неравенство легко решается итерацией. Можно применить подручные средства, калькулятор, или, например, Excel.
Уже при n = 7 имеем: 8*lg(n) = 6,76
Оценки можно получить и исследуя неравенство: 10^n >= n^8
n ! n^8 ! 10^n
----+----------+----------
6 ! 1679616 ! 1000000
7 ! 5764801 ! 10000000
----+----------+----------


Как-то так, ...

[Аватар]

Не согласен, что равенство ошибка. Приближенно решив его и взяв ближайшее большее целое от решения и найдем то, что ищем. 8-ка решение, кажись

[type_Oleg]

А логарифм - десятичный ?

[Аватар]

Коль lg, то десятичній. Наверно. Из этого исходил

[vi0]

Сообщение от type_Oleg

А логарифм - десятичный ?

это сортировка слиянием - деление пополам, поэтому логарифм с основанием 2

[digitalis]

так и надо было пис'ать. lg - десятичный логарифм, log2 - по основанию 2.

[Serge_Bliznykov]

а зачем подняли тему 2014 года?
Думаете, ещё важно, какой там в задании логарифм был?

[digitalis]

Ой, не заметил vi0 - это все он, а я повелся ... Дык тему закрыли бы - и усе.