On asymptotic estimates for arithmetic cost functions-猫眼课题宝

关于算术成本函数的渐近估计

DOI：

发表时间：

1997

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

C. Moreira

令Or（n）（n的成本）是从1开始获得n所需的最小算术运算次数。我们证明，或（n）> log n -log log n的几乎所有的n E N，和，给定？> 0，或（n）1存在i，j，0 0，则对几乎所有的n C N有T（（n）>（loglo~gn）l+e.在这里，我们通过证明以下内容改进了上述结果：对于几乎所有n c N，我们有Tr（n）> lolg并且，对于任何给定的E > 0，我们有T（（n）0，{T（n）> logn +（1 -）log nloglog logn对于几乎所有n c N，log log n（log log n）2 T（（n）< log n +（3 + s log n log log log n对于n足够大。log log n（log log n）2 foiag nuh此外，第一个不等式不依赖于我们可以使用的二进制运算的数量（假设这个数量是有限的）。编辑于1994年10月25日收到，修订版于1995年8月15日收到。1991年数学学科分类。小学11 Y16;中学68 Q25、68 Q15、11B 75。1997年美国数学学会

Let Or(n) (the cost of n) be the minimum number of arithmetic operations needed to obtain n starting from 1. We prove that Or(n) > log n -log log n for almost all n E N, and, given ? > 0, Or(n) 1 there are i, j, 0 0, we have T((n) > (loglo~gn)l+e for almost all n C N . Here we improve the above results, by proving the following: For almost all n c N we have Tr(n) > lolg nand, for any given E > 0, we have T((n) 0, {T(n) > logn + (1 -)log nloglog logn for almost all n c N, log log n (log log n) 2 T((n) < log n + (3 + s log n log log log n for n large enough. log log n (log log n) 2 foiag nuh Moreover, the first inequality does not depend on the number of binary operations that we can use (provided that this number is finite). Received by the editors October 25, 1994 and, in revised form, August 15, 1995. 1991 Mathematics Subject Classification. Primary 11Y16; Secondary 68Q25, 68Q15, 11B75. ( 1997 American Mathematical Society

On asymptotic estimates for arithmetic cost functions

关于算术成本函数的渐近估计

文献摘要

被引文献

相似文献