Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Произвести вычисления с числами у которых большая степень
СообщениеДобавлено: 20 май 2017, 23:24 
Не в сети
Начинающий
Зарегистрирован:
20 май 2017, 23:02
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте!
Не могу понять как произвести такие вычисления
Нужно посчитать во сколько один алгоритм быстрее другого для 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
Прошу о помощи и заранее благодарю!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 20 май 2017, 23:53 
Не в сети
Начинающий
Зарегистрирован:
20 май 2017, 23:02
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте!
Не могу понять как произвести такие вычисления
Нужно посчитать во сколько один алгоритм быстрее другого для 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
Прошу о помощи и заранее благодарю!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 00:59 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3186
Cпасибо сказано: 55
Спасибо получено:
697 раз в 630 сообщениях
Очков репутации: 201

Добавить очки репутацииУменьшить очки репутации
Наверное не требуется точных вычислений. Достаточно прикинуть порядок.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 01:29 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1148
Cпасибо сказано: 61
Спасибо получено:
322 раз в 306 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
У меня получается [math]\frac{0{,}25\cdot21^{12}}{73{,}78}\approx25\cdot10^{12}[/math], а [math]\frac{I}{Q}=\frac{n}{5{,}6\log_2n}[/math]. И в чем именно вам нужна помощь?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 15:38 
Не в сети
Начинающий
Зарегистрирован:
20 май 2017, 23:02
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
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, 16:33, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 16:28 
Не в сети
Начинающий
Зарегистрирован:
20 май 2017, 23:02
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Наверное не требуется точных вычислений. Достаточно прикинуть порядок.

Как его прикинуть?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 19:26 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1148
Cпасибо сказано: 61
Спасибо получено:
322 раз в 306 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
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].

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Произвести вычисления, пользуясь прав-мы действий над компл

в форуме Линейная и Абстрактная алгебра

helpmepleaseeee

1

56

31 май 2017, 07:17

Произвести превращение

в форуме Дискретная математика, Теория множеств и Логика

Nicolay_8

1

127

26 сен 2014, 21:06

Как произвести триангуляцию по Дирихле?

в форуме Дифференциальные и Интегральные уравнения

rny

1

157

18 ноя 2015, 09:12

Произвести выборку из 200 значений

в форуме Теория вероятностей

benni1391

6

489

10 май 2013, 20:32

Как произвести сглаживание графика

в форуме MathCad

96BlueWater

2

161

29 дек 2016, 02:34

Произвести исследование следующих функций

в форуме Пределы числовых последовательностей и функций, Исследования функций

YANA--

3

156

14 янв 2015, 18:38

Теория алгоритмов

в форуме Информатика и Компьютерные науки

Stasya7

2

304

28 мар 2015, 18:31

Теория алгоритмов

в форуме Дискретная математика, Теория множеств и Логика

Veltare

1

33

30 ноя 2017, 13:32

Теория алгоритмов

в форуме Дискретная математика, Теория множеств и Логика

Mariha

1

361

05 ноя 2013, 19:07

По теории алгоритмов

в форуме Дискретная математика, Теория множеств и Логика

Len4ik_pik_pik

0

127

26 ноя 2014, 18:48


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved