Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
Сравнить скорости двух алгоритмов.Произвести вычисления http://mathhelpplanet.com/viewtopic.php?f=44&t=54591 |
Страница 1 из 1 |
Автор: | Spoko [ 20 май 2017, 22:24 ] |
Заголовок сообщения: | Произвести вычисления с числами у которых большая степень |
Здравствуйте! Не могу понять как произвести такие вычисления Нужно посчитать во сколько один алгоритм быстрее другого для 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 [ 20 май 2017, 22:53 ] |
Заголовок сообщения: | Сравнить скорости двух алгоритмов.Произвести вычисления |
Здравствуйте! Не могу понять как произвести такие вычисления Нужно посчитать во сколько один алгоритм быстрее другого для 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 [ 20 май 2017, 23:59 ] |
Заголовок сообщения: | Re: Сравнить скорости двух алгоритмов.Произвести вычисления |
Наверное не требуется точных вычислений. Достаточно прикинуть порядок. |
Автор: | 3D Homer [ 21 май 2017, 00:29 ] |
Заголовок сообщения: | Re: Сравнить скорости двух алгоритмов.Произвести вычисления |
У меня получается [math]\frac{0{,}25\cdot21^{12}}{73{,}78}\approx25\cdot10^{12}[/math], а [math]\frac{I}{Q}=\frac{n}{5{,}6\log_2n}[/math]. И в чем именно вам нужна помощь? |
Автор: | Spoko [ 21 май 2017, 14:38 ] |
Заголовок сообщения: | Re: Сравнить скорости двух алгоритмов.Произвести вычисления |
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:28 ] |
Заголовок сообщения: | Re: Сравнить скорости двух алгоритмов.Произвести вычисления |
swan писал(а): Наверное не требуется точных вычислений. Достаточно прикинуть порядок. Как его прикинуть? |
Автор: | 3D Homer [ 21 май 2017, 18:26 ] |
Заголовок сообщения: | Re: Сравнить скорости двух алгоритмов.Произвести вычисления |
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]. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |