知识卡片

普通读书笔记卡 · 1708.b.3.c · 生成模型:未记录

常数成本是分析模型假设

理解等级:中级

估算算法运行时间时,可以先假定基本操作具有某种固定成本,再研究输入规模增长时的主导项;这使不同方案的增长趋势可比较。

原文称所有平台上这些常数都小到可忽略,不能作为普遍事实。现实中缓存、分配、输入类型、I/O或语言实现可能改变成本,某些操作也随数据位宽或大小增长。渐近分析与测量需各自标明模型和范围。

31将比较k位整数视为O(1),条件是k固定不随问题规模改变。若k作为输入规模变化,大整数表示及比较所需工作也可能随k增长;不能把固定机器字的近似直接推广为任意精度整数。

50引出处理器整数运算、浮点单元与IEEE754表示;速度和语义依赖数据类型、硬件、编译器及运算,不能仅据“整数通常高效”断言所有情况下整数都比浮点快。后续章节再按具体示例讨论舍入、比较和特殊值。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      常数时间,但是最终我们得到抽象结论的时候,都会忽略这些常数时间。在所有的平台上,相比影响本书所述的算法性能的其他因素来说,这些常数都是小到可以忽略不计的。

    • · 查看原书依据

      256位的数字时,性能表现又如何呢?1024位呢?我们认为在给定k的前提下,比较两个k位的数字的操作将在常数时间内完成。关键在于问题的规模(例如x、y的值)不可能超过k。我们把额外的工作,例如k的倍增,也抽象为O(1)的性能。

    • · 查看原书依据

      浮点数,当然这些浮点数必须遵守IEEE关于二进制浮点算数的标准(IEEE754)。 整数值(如布尔型、8位短整型,以及16位或者32位整数)的计算通常能被处理器高效地执行。高效程序一般都会利用浮点数和整数算术的性能差异来改善程序的执行效率。当编写含有浮点计算的程序的时候,有一些问题是软件开发人员必须

    参考来源

    - 位置:《算法技术手册》第2章《第2章 算法的数学原理》(spine1461;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1425.html;u023-ch02-004)。 - 结论依据:23全文常数时间假设实读;明确指出对所有平台都小可忽略的断言缺少条件。 - 原始内容:常数时间,但是最终我们得到抽象结论的时候,都会忽略这些常数时间。在所有的平台上,相比影响本书所述的算法性能的其他因素来说,这些常数都是小到可以忽略不计的。 - 位置:《算法技术手册》第2章《讨论0:常数级算法的性能》(spine1466;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1430.html;u031-ch02-004)。 - 结论依据:31将比较k位整数视为O(1),条件是k固定不随问题规模改变。若k作为输入规模变化,大整数表示及比较所需工作也可能随k增长;不能把固定机器字的近似直接推广为任意精度整数。 - 原始内容:256位的数字时,性能表现又如何呢?1024位呢?我们认为在给定k的前提下,比较两个k位的数字的操作将在常数时间内完成。关键在于问题的规模(例如x、y的值)不可能超过k。我们把额外的工作,例如k的倍增,也抽象为O(1)的性能。 - 位置:《算法技术手册》第3章《浮点计算》(spine1483;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1447.html;u050-ch02-004)。 - 结论依据:50引出处理器整数运算、浮点单元与IEEE754表示;速度和语义依赖数据类型、硬件、编译器及运算,不能仅据“整数通常高效”断言所有情况下整数都比浮点快。后续章节再按具体示例讨论舍入、比较和特殊值。 - 原始内容:浮点数,当然这些浮点数必须遵守IEEE关于二进制浮点算数的标准(IEEE754)。 整数值(如布尔型、8位短整型,以及16位或者32位整数)的计算通常能被处理器高效地执行。高效程序一般都会利用浮点数和整数算术的性能差异来改善程序的执行效率。当编写含有浮点计算的程序的时候,有一些问题是软件开发人员必须