Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 7 ] |
|
Автор | Сообщение | |
---|---|---|
Spoko |
|
|
Не могу понять как произвести такие вычисления Нужно посчитать во сколько один алгоритм быстрее другого для n =21^12(в данном случае Quicksort и Insertsort) Имеются даже готовые вычисления,но никак не могу понять, как посчитать это самостоятельно, на экзамене.Особенно как эту часть то самому посчитать ([math]\frac{ 0.25*21^{12} }{ 73.78 }[/math]=23926058780206) Quicksort: A(n)=1,4nlog2(n) InsertSort: A(n)=(1/4)*(n^2) I/Q= [math]\frac{ 0.25*21^{12}*21^{12} }{ 1.4*21^{12}*\log_{2}{21^{12} } }[/math]=[math]\frac{ 0.25*21^{12} }{ 16.8*4.392 }[/math]=[math]\frac{ 0.25*21^{12} }{ 73.78 }[/math]=23926058780206=24*10[math]^{11}[/math] Общий вид : I/Q = n/(7*log2(n)); И есть такой пример (с n=2[math]^{24}[/math] I/Q= [math]\frac{ 0,25*2^{24}*2^{24} }{ 1,4*2^{24}*\log_{2}{2^{24} } }[/math]=[math]\frac{0,25*2^{24} }{ 1.4*24*\log_{2}{2} }[/math]=[math]\frac{ 0,25*2^{24} }{33,6 }[/math]=0,0074*2[math]^{24}[/math]=124151,4 Прошу о помощи и заранее благодарю! |
||
Вернуться к началу | ||
Spoko |
|
|
Здравствуйте!
Не могу понять как произвести такие вычисления Нужно посчитать во сколько один алгоритм быстрее другого для n =21^12(в данном случае Quicksort и Insertsort) Имеются даже готовые вычисления,но никак не могу понять, как посчитать это самостоятельно, на экзамене.Особенно как эту часть то самому посчитать ([math]\frac{ 0.25*21^{12} }{ 73.78 }[/math]=23926058780206) Quicksort: A(n)=1,4nlog2(n) InsertSort: A(n)=(1/4)*(n^2) I/Q= [math]\frac{ 0.25*21^{12}*21^{12} }{ 1.4*21^{12}*\log_{2}{21^{12} } }[/math]=[math]\frac{ 0.25*21^{12} }{ 16.8*4.392 }[/math]=[math]\frac{ 0.25*21^{12} }{ 73.78 }[/math]=23926058780206=24*10[math]^{11}[/math] Общий вид : I/Q = n/(7*log2(n)); И есть пример деления наоборот: И есть такой пример (с n=2^24) I/Q= [math]\frac{ 0,25*2^{24}*2^{24} }{ 1,4*2^{24}*\log_{2}{2^{24} } }[/math]=[math]\frac{0,25*2^{24} }{ 1.4*24*\log_{2}{2} }[/math]=[math]\frac{ 0,25*2^{24} }{33,6 }[/math]=0,0074*2[math]^{24}[/math]=124151,4 Прошу о помощи и заранее благодарю! |
||
Вернуться к началу | ||
swan |
|
|
Наверное не требуется точных вычислений. Достаточно прикинуть порядок.
|
||
Вернуться к началу | ||
3D Homer |
|
|
У меня получается [math]\frac{0{,}25\cdot21^{12}}{73{,}78}\approx25\cdot10^{12}[/math], а [math]\frac{I}{Q}=\frac{n}{5{,}6\log_2n}[/math]. И в чем именно вам нужна помощь?
|
||
Вернуться к началу | ||
Spoko |
|
|
3D Homer писал(а): У меня получается [math]\frac{0{,}25\cdot21^{12}}{73{,}78}\approx25\cdot10^{12}[/math], а [math]\frac{I}{Q}=\frac{n}{5{,}6\log_2n}[/math]. И в чем именно вам нужна помощь? Меня интересует как из этого [math]\frac{ 0.25*21^{12} }{73.78 }[/math] получить вот это 25*10[math]^{12}[/math] без калькулятора . В дроби у нас число со степенью 12(которое даже на калькуляторе обычном не посчитаешь, не то что на экзамене), а после "равно" уже число умноженное на 10 в степени 12.Как такие расчёты произвести без онлайн калькулятора ?Скорее всего я не знаю какого-то важного математического свойства,но какого... Благодарю за отзывчивость Последний раз редактировалось Spoko 21 май 2017, 15:33, всего редактировалось 1 раз. |
||
Вернуться к началу | ||
Spoko |
|
|
swan писал(а): Наверное не требуется точных вычислений. Достаточно прикинуть порядок. Как его прикинуть? |
||
Вернуться к началу | ||
3D Homer |
|
|
Spoko писал(а): Меня интересует как из этого [math]\frac{ 0.25*21^{12} }{73.78 }[/math] получить вот это 25*10[math]^{12}[/math] без калькулятора . Я вычислил это на калькуляторе. Без калькулятора можно получить ответ с точностью до порядка. Например,[math]\frac{ 0.25*21^{12} }{73.78 }\approx\frac{20^{12}}{4\cdot75}=\frac{2^{12}10^{12}}{4\cdot75}=\frac{2^{10}\cdot10^{12}}{75}\approx\frac{1000\cdot 10^{12}}{75}=\frac{40\cdot10^{12}}{3}\approx13\cdot10^{12}[/math] Ошибка примерно в 2 раза. Но, как было сказано, сложности алгоритмов сравнивают обычно с точностью до о-большого или о-малого. Здесь [math]1{,}4n\log n=o(n^2 \slash 4)[/math]. |
||
Вернуться к началу | ||
[ Сообщений: 7 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Произвести вычисления, пользуясь прав-мы действий над компл
в форуме Линейная и Абстрактная алгебра |
1 |
243 |
31 май 2017, 06:17 |
|
Сравнить МНК-оценки и остатки двух регрессий | 0 |
169 |
08 май 2021, 14:30 |
|
Метрика для вычисления отличия двух функций | 4 |
170 |
20 сен 2022, 16:48 |
|
Произвести превращение | 1 |
310 |
26 сен 2014, 20:06 |
|
Как произвести сглаживание графика
в форуме MathCad |
2 |
512 |
29 дек 2016, 01:34 |
|
Как произвести триангуляцию по Дирихле? | 1 |
351 |
18 ноя 2015, 08:12 |
|
Произвести исследование следующих функций
в форуме Пределы числовых последовательностей и функций, Исследования функций |
3 |
290 |
14 янв 2015, 17:38 |
|
Теория алгоритмов | 0 |
362 |
25 мар 2014, 11:51 |
|
Классификация алгоритмов
в форуме Информатика и Компьютерные науки |
0 |
196 |
03 июн 2021, 15:18 |
|
Теория алгоритмов | 1 |
311 |
30 ноя 2017, 12:32 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |