知识卡片

普通读书笔记卡 · 3694

大整数算法按输入位数计复杂度

理解等级:中级

数论算法常处理少量却很大的整数,输入规模应按二进制位数衡量。

把加减乘除都当作单位时间会低估成本;朴素乘法、除法对β位数通常需Θ(β²)位操作。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第31章 数论算法 · 查看原书依据

      Because we’ll be working with large integers, we need to adjust how to think about the size of an input and about the cost of elementary arithmetic operations. In this chapter, a “large input” typically means an input containing “large integers” rather than an input containing “many integers” (as for sorting). Thus, the size of an input depends on the number of bits required to represent that input, not just the number of integers in the input. An algorithm with

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[0,5000))。 - 结论依据:原文定义整除、素数、余数、同余类和最大公约数,或给出相应定理;公式图已核对。 - 原始内容:Because we’ll be working with large integers, we need to adjust how to think about the size of an input and about the cost of elementary arithmetic operations. In this chapter, a “large input” typically means an input containing “large integers” rather than an input containing “many integers” (as for sorting). Thus, the size of an input depends on the number of bits required to represent that input, not just the number of integers in the input. An algorithm with