Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 29.01.2014, 16:56   #1
Эйнж
 
Аватар для Эйнж
 
Регистрация: 02.08.2008
Сообщений: 9
По умолчанию Вопрос про логарифм

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

вопрос, как дальше ? или ход мыслей не верный.
Эйнж вне форума Ответить с цитированием
Старый 29.01.2014, 17:38   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

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

Последний раз редактировалось Аватар; 29.01.2014 в 17:43.
Аватар вне форума Ответить с цитированием
Старый 29.01.2014, 20:55   #3
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

В данном случае ошибка в том, что пишется равенство.
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
----+----------+----------


Как-то так, ...
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 29.01.2014, 21:00   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Не согласен, что равенство ошибка. Приближенно решив его и взяв ближайшее большее целое от решения и найдем то, что ищем. 8-ка решение, кажись
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 29.01.2014, 21:23   #5
type_Oleg
Старожил
 
Аватар для type_Oleg
 
Регистрация: 02.03.2008
Сообщений: 2,538
По умолчанию

А логарифм - десятичный ?
type_Oleg вне форума Ответить с цитированием
Старый 29.01.2014, 21:24   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Коль lg, то десятичній. Наверно. Из этого исходил
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 13.07.2018, 16:06   #7
vi0
Новичок
Джуниор
 
Регистрация: 13.07.2018
Сообщений: 1
По умолчанию

Цитата:
Сообщение от type_Oleg Посмотреть сообщение
А логарифм - десятичный ?
это сортировка слиянием - деление пополам, поэтому логарифм с основанием 2
vi0 вне форума Ответить с цитированием
Старый 14.07.2018, 10:38   #8
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,534
По умолчанию

так и надо было пис'ать. lg - десятичный логарифм, log2 - по основанию 2.
digitalis вне форума Ответить с цитированием
Старый 14.07.2018, 11:34   #9
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

а зачем подняли тему 2014 года?
Думаете, ещё важно, какой там в задании логарифм был?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 14.07.2018, 12:38   #10
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,534
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вопрос про Свойство Visible и про иконки в imagelist Kappi4 Компоненты Delphi 2 21.05.2010 13:10
Вопрос про C# BanzoO Общие вопросы C/C++ 1 02.07.2009 03:47
вопрос по математическим функциям - десятичный логарифм. на log10(x) marisha Помощь студентам 1 13.12.2008 10:14
Вопрос наверное про функции, а так точно даже не знаю про что. (Вопрос начинющего #6) Albert2008 Общие вопросы Delphi 4 21.08.2008 15:33
У меня вопрос про базы данных,а точнее про таблицы!!! Alexij Общие вопросы Delphi 1 13.04.2008 23:24