Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | |
---|---|---|
progphp |
|
|
Итак, сравниваются скорость работы двух алгоритмов сортировки(методом вставки и слияния), скорость первого алгоритма оценивается как 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 ... |
||
Вернуться к началу | ||
3D Homer |
|
|
Насколько я понимаю, уравнение [math]n=8\log_2n[/math] не решается в элементарных функциях, но приблизительное решение [math]n=43{,}56[/math].
|
||
Вернуться к началу | ||
swan |
|
|
Посмыслу у нас n - натуральное, функция слева растет быстрее, чем справа, так что можно и просто подобрать.
|
||
Вернуться к началу | ||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Теория алгоритмов | 1 |
311 |
30 ноя 2017, 12:32 |
|
Теория алгоритмов | 0 |
330 |
13 ноя 2015, 06:21 |
|
Теория алгоритмов
в форуме Информатика и Компьютерные науки |
2 |
590 |
28 мар 2015, 17:31 |
|
Математическая логика и теория алгоритмов | 0 |
80 |
27 ноя 2023, 21:49 |
|
Теория алгоритмов: детерминированные конечные автоматы | 1 |
179 |
07 апр 2022, 21:22 |
|
Доказать очевидное. Языки, теория алгоритмов | 5 |
309 |
14 сен 2014, 16:03 |
|
Теория алгоритмов. Построить нормальный алгорифм | 0 |
461 |
23 ноя 2014, 17:53 |
|
По теории алгоритмов | 0 |
353 |
26 ноя 2014, 17:48 |
|
Классификация алгоритмов
в форуме Информатика и Компьютерные науки |
0 |
197 |
03 июн 2021, 15:18 |
|
Задание по теории алгоритмов | 10 |
461 |
25 окт 2016, 22:34 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |