|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
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
Сообщений: 18,922
|
Меняя в цикле 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 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,312
|
В данном случае ошибка в том, что пишется равенство.
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 ----+----------+---------- Как-то так, ...
Как-то так, ...
|
29.01.2014, 21:00 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Не согласен, что равенство ошибка. Приближенно решив его и взяв ближайшее большее целое от решения и найдем то, что ищем. 8-ка решение, кажись
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
29.01.2014, 21:23 | #5 |
Старожил
Регистрация: 02.03.2008
Сообщений: 2,499
|
А логарифм - десятичный ?
|
29.01.2014, 21:24 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Коль lg, то десятичній. Наверно. Из этого исходил
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
13.07.2018, 16:06 | #7 |
Новичок
Джуниор
Регистрация: 13.07.2018
Сообщений: 1
|
|
14.07.2018, 10:38 | #8 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,567
|
так и надо было пис'ать. lg - десятичный логарифм, log2 - по основанию 2.
|
14.07.2018, 11:34 | #9 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
а зачем подняли тему 2014 года?
Думаете, ещё важно, какой там в задании логарифм был? |
14.07.2018, 12:38 | #10 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,567
|
Ой, не заметил vi0 - это все он, а я повелся ... Дык тему закрыли бы - и усе.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вопрос про Свойство 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 |