Математический форум 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/