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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Теория алгоритмов
СообщениеДобавлено: 11 фев 2016, 23:17 
Не в сети
Начинающий
Зарегистрирован:
21 май 2015, 00:02
Сообщений: 34
Cпасибо сказано: 11
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте, есть такая задачка, полное условие приводить не стану, загвоздка как раз в решении неравенства.
Итак, сравниваются скорость работы двух алгоритмов сортировки(методом вставки и слияния), скорость первого алгоритма оценивается как 8[math]n^{2}[/math] а другого 64n[math]\log_{2}{n}[/math], нужно найти минимальное n (число элементов в массиве), при котором будет выполнятся неравенство
8[math]n^{2}[/math] [math]>[/math] 64n[math]\log_{2}{n}[/math], как нетрудно заметить, после преобразования получим
n [math]>[/math] 8[math]\log_{2}{n}[/math], и так же легко заметить что при n=64 это неравенство уже выполняется, т.е. первый алгоритм оказывается медленней. А как решить это неравенство в общем виде?Возможно, оно выполняется и при n=59 или 48 ...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория алгоритмов
СообщениеДобавлено: 11 фев 2016, 23:31 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Насколько я понимаю, уравнение [math]n=8\log_2n[/math] не решается в элементарных функциях, но приблизительное решение [math]n=43{,}56[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория алгоритмов
СообщениеДобавлено: 12 фев 2016, 00:23 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Посмыслу у нас n - натуральное, функция слева растет быстрее, чем справа, так что можно и просто подобрать.

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Теория алгоритмов

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

Veltare

1

311

30 ноя 2017, 12:32

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

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

sergeiomsk1

0

330

13 ноя 2015, 06:21

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

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

Stasya7

2

590

28 мар 2015, 17:31

Математическая логика и теория алгоритмов

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

LaMa

0

80

27 ноя 2023, 21:49

Теория алгоритмов: детерминированные конечные автоматы

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

frei69

1

179

07 апр 2022, 21:22

Доказать очевидное. Языки, теория алгоритмов

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

letunx

5

309

14 сен 2014, 16:03

Теория алгоритмов. Построить нормальный алгорифм

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

olyakosyura

0

461

23 ноя 2014, 17:53

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

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

Len4ik_pik_pik

0

353

26 ноя 2014, 17:48

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

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

crub34

0

197

03 июн 2021, 15:18

Задание по теории алгоритмов

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

melika

10

461

25 окт 2016, 22:34


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



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

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


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

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

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

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