8
A
回答
12
欧几里得算法(计算gcd
)非常快。当从[1, n]
随机统一绘制两个数字时,计算其gcd
的平均步数为O(log n)
。每个步骤所需的平均计算时间是数字的二次方。
还有一些替代品的性能稍好些(即每个步骤在数字位数上都是次级的),但它们只对非常大的整数有效。例如参见On Schönhage's algorithm and subquadratic integer gcd computation。
7
如果您使用的分部/余料明显比班次更贵,请考虑使用binary GCD。
相关问题
- 1. 什么是最快的方法来检查给定的数组是否有数组或两个值?
- 2. 检查一个类是否定义了函数的最快方法是什么?
- 3. 检查两个条件是否为真的最快方法是什么?
- 4. 检查两个Tbitmap是否相同的最快方法是什么?
- 5. 什么是检查文件是否改变的最快方法?
- 6. 检查号码重复数字的最快方法是什么?
- 7. 检查两个数字是否相等的最佳方法
- 8. Tcl:什么是检查空白字符串的最快方法
- 9. 检查两个CRgn是否相交的最简单方法是什么?
- 10. 什么是最快的方式来检查一个数字是否在python的特定范围内?
- 11. 什么是检查svn工作副本是否有变化的最快方法?
- 12. 算法:什么是检查集合包含的最快方法?
- 13. 在桶中查找数字的最快方法是什么?
- 14. 查找数字最快的方法是什么?
- 15. 检查另一个字符串是否存在的最佳方法是什么?
- 16. 检查视窗是否可见的最佳方法是什么?
- 17. 检查FileInputStream是否关闭的最佳方法是什么?
- 18. 什么是检查PDO是否存在的最佳方法
- 19. 检查一个字符串是否包含Python 3中重复字符的最快方法是什么?
- 20. 什么是MySQL的最快的方法来检查外国REFFERENCE
- 21. 找到n个数字的gcd最快的方法是什么?
- 22. 什么是两个字节之间的特定位操作的最快方法?
- 23. 检查是否可以解析字符串的最快方法
- 24. 检查两幅图像是否相同的最简单方法是什么?
- 25. 检查两个数字是否接近相等的最简单方法是什么?
- 26. 什么是更好的方法来检查一个数字是否为总数?
- 27. 什么是检查mongodb文档存在的最快方法?
- 28. 在Python中检查重复项的最快方法是什么?
- 29. 检查SQL Server可用性的最快方法是什么?
- 30. 什么是检查类型的最快方法?
我想评论一下,测算算术算法的复杂性时不考虑算术运算的成本,这有点粗糙。 – 2009-09-27 12:03:11
当两个数字是斐波那契数列中的连续条目时,最差步数#也是O(log n)。 – 2009-09-27 13:26:31
@Pavel Shved:我确实考虑了成本。比照“每个步骤所需的平均计算时间是数字的二次方”。 – jason 2009-09-27 19:16:15