|
Дискретная математика, 1994, том 6, выпуск 2, страницы 129–137
(Mi dm628)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О вычислении наборов степеней
В. В. Кочергин
Аннотация:
Исследуется известная задача [4, разд. 4.6.3, упр. 32] о сложности вычисления наборов значений $x^{n_1},\dots,x^{n_m}$ для различных наборов показателей $(n_1,\dots,n_m)$. Пусть $l(x^{n_1},\dots,x^{n_m})$ — наименьшее число операций умножения, достаточное для вычисления набора степеней $x^{n_1},\dots$,$x^{n_m}$, а $L(n_1,\dots,n_m)=\max l(x^{k_1},\dots,x^{k_m})$, где максимум берется по всем наборам $(k_1,\dots,k_m)$, $1\le k_i\le n_i$, $i=1,\dots,m$. Доказано, что если последовательность наборов вида $\tilde n=(n_1,\dots,n_m)$ удовлетворяет условию
$$
m+\log_{2}(\max\,\{n_{1},\ldots,n_{m}\})
=o\left(\frac{\log_{2}\prod_{i=1}^mn_{i}}{\log_{2}\log_{2}\prod_{i=1}^mn_i}\right),
$$
то
$$
L(n_{1},\ldots,n_{m})\sim\frac{\log_{2}\prod_{i=1}^mn_{i}}{\log_{2}\log_{2}\prod_{i=1}^mn_{i}},
$$
причем
$$
l(x^{k_{1}},\ldots, x^{k_{m}})\sim\frac{\log_{2}\prod_{i=1}^mk_{i}}{\log_{2}\log_{2}\prod_{i=1}^mk_{i}}
$$
для почти всех наборов $(k_1,\dots,k_m)$ таких, что $1\le k_i\le n_i$, $i=1,\dots,m$.
Статья поступила: 15.05.1992
Образец цитирования:
В. В. Кочергин, “О вычислении наборов степеней”, Дискрет. матем., 6:2 (1994), 129–137; Discrete Math. Appl., 4:2 (1994), 119–128
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm628 https://www.mathnet.ru/rus/dm/v6/i2/p129
|
Статистика просмотров: |
Страница аннотации: | 298 | PDF полного текста: | 117 | Первая страница: | 1 |
|