 Возведение в степень., Верхняя оценка. |
Рейтинг
 |
 |
Добро пожаловать, гость ( Вход | Регистрация )
Правила раздела
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
| nik_vic |
  22.1.2008, 11:11
Сообщение
#1
|
|
Активный участник  Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125  |
Есть известная задача о минимальном количестве умножений для возведения в натуральную степень n с оценками log2(n) и 2log2(n).
Известна ли в качестве верхней оценки log2(n)*(1+о(1))? С уважением, НикВик. -------------------- Где это видано?
|
   |
 
|
  |
Ответов
| Geen |
22.1.2008, 14:22
Сообщение
#2
|
|
Участник Группа: Пользователи Braingames Сообщений: 52 Регистрация: 29.5.2007 Пользователь №: 1 027 |
o(1) это 0. Особенно, если его прибавлять/сравнивать с 1.
 |
|
|
|
| nik_vic |
22.1.2008, 14:27
Сообщение
#3
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(Geen @ 22.1.2008, 14:22)  o(1) это 0. Особенно, если его прибавлять/сравнивать с 1. Ладно, переформулирую - предел отношения минимальное_число_умножений_для_возведения_в_степень_n / log2(n) равен 1. -------------------- Где это видано?
|
|
|
|
| waldian |
22.1.2008, 15:38
Сообщение
#4
|
 Активный участник Группа: Пользователи Braingames Сообщений: 813 Регистрация: 20.4.2007 Из: Питер Пользователь №: 103 |
Был вроде древовидный алгоритм.. И вроде бы его можно заточить под определенный диапазон степеней (достаточно большой), тогда на них он будет давать похожую сложность.
|
|
|
|
| nik_vic |
22.1.2008, 15:58
Сообщение
#5
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(waldian @ 22.1.2008, 15:38) Был вроде древовидный алгоритм.. И вроде бы его можно заточить под определенный диапазон степеней (достаточно большой), тогда на них он будет давать похожую сложность. Поставлю вопрос ещё более конкретно - в какое число умножений можно "уложиться" при возведении в степени, число бит которых не превосходит, скажем, 1000? "Стандарт" даёт 1998 - 999 возведений в квадрат и 999 умножений на аргумент. Я умею за 1230... Кто меньше?  -------------------- Где это видано?
|
|
|
|
| waldian |
22.1.2008, 20:46
Сообщение
#6
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 813 Регистрация: 20.4.2007 Из: Питер Пользователь №: 103 |
QUOTE(nik_vic @ 22.1.2008, 15:58) Не слышал ничего такого - кроме стандартного для начинающих программистов. Поставлю вопрос ещё более конкретно - в какое число умножений можно "уложиться" при возведении в степени, число бит которых не превосходит, скажем, 1000? "Стандарт" даёт 1998 - 999 возведений в квадрат и 999 умножений на аргумент. Я умею за 1230... Кто меньше? Только все убыстрения являются разменом времени на память. Так что, надо критерий четче ставить. |
|
|
|
| nik_vic |
22.1.2008, 21:00
Сообщение
#7
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(waldian @ 22.1.2008, 20:46) Только все убыстрения являются разменом времени на память. Так что, надо критерий четче ставить. Задача сформулирована однозначно. Впрочем, меня больше интересует, не слышал ли кто-нибудь что-то подобное. -------------------- Где это видано?
|
|
|
|
Сообщения в этой теме
nik_vic Возведение в степень. 22.1.2008, 11:11
Geen Прошу прощения, а что такое 1+o(1)? (о малое?) 22.1.2008, 11:52
nik_vic
Прошу прощения, а что такое 1+o(1)? (о малое?)
Че... 22.1.2008, 12:36 Geen
Гм, обозначение достаточно стандартно.
Ладно, пер... 22.1.2008, 23:52 Mouse эта задача не связанна с какой-то гипотизой в мате... 22.1.2008, 20:57 nik_vic
эта задача не связанна с какой-то гипотизой в мат... 25.1.2008, 10:38 waldian Нет.
Хотя не исключаю, что задача построения мин... 25.1.2008, 14:03 nik_vic
А минимизирующая схема вроде решается проще... Вр... 25.1.2008, 14:14 waldian
В некотором смысле задача похожа на построение м... 25.1.2008, 17:02 nik_vic
"NP-универсальна" - это NP-полная или N... 25.1.2008, 17:12 nik_vic Пожалуй, дам решение. Чтобы почти без формул, для ... 27.1.2008, 20:13 Mouse 1. размеры памяти хоть залейся в разумных приделах... 22.1.2008, 23:44 nik_vic
1. размеры памяти хоть залейся в разумных придела... 23.1.2008, 9:08 Mouse
это стандартное обозначение, просто в програмиров... 23.1.2008, 0:04 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0 -
|
Упрощённая версия | Сейчас: 20.7.2025, 6:24 |
Invision Power Board
v2.1.4 © 2025 IPS, Inc.