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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Произвести вычисления с числами у которых большая степень
СообщениеДобавлено: 20 май 2017, 22:24 
Не в сети
Начинающий
Зарегистрирован:
20 май 2017, 22: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, 22:53 
Не в сети
Начинающий
Зарегистрирован:
20 май 2017, 22: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: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 20 май 2017, 23:59 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 00:29 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2588
Cпасибо сказано: 103
Спасибо получено:
744 раз в 699 сообщениях
Очков репутации: 158

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сравнить скорости двух алгоритмов.Произвести вычисления
СообщениеДобавлено: 21 май 2017, 18:26 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2588
Cпасибо сказано: 103
Спасибо получено:
744 раз в 699 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
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пасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 7 ]

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

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

helpmepleaseeee

1

243

31 май 2017, 06:17

Сравнить МНК-оценки и остатки двух регрессий

в форуме Математическая статистика и Эконометрика

Rn00b

0

169

08 май 2021, 14:30

Метрика для вычисления отличия двух функций

в форуме Математическая статистика и Эконометрика

marauder94

4

170

20 сен 2022, 16:48

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

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

Nicolay_8

1

310

26 сен 2014, 20:06

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

в форуме MathCad

96BlueWater

2

512

29 дек 2016, 01:34

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

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

rny

1

351

18 ноя 2015, 08:12

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

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

YANA--

3

290

14 янв 2015, 17:38

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

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

junkfatality

0

362

25 мар 2014, 11:51

Классификация алгоритмов

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

crub34

0

196

03 июн 2021, 15:18

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

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

Veltare

1

311

30 ноя 2017, 12:32


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



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

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


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

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

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

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