知识卡片

普通读书笔记卡 · 5654.c.1.a

基本操作计数需要成本模型

理解等级:中级

复杂度分析先约定什么算作基本操作,再统计它随输入规模执行多少次。省略固定系数和低阶项后,可以得到更容易比较的渐近增长描述。

这不表示真实机器上加法、打印和任意长字符串操作耗时相同。把它们都当单位成本只适合明确的简化模型;若某项操作本身随数据长度增长,就要把这部分成本算入循环体。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      计算操作运行时间统计”简化为“计算操作数量统计” ,这样一来估算难度就大大降低了。 ‧ 时间复杂度也存在一定的局限性。例如,尽管算法A C 的时间复杂度相同,但实际运行时间差别很 大。同样,尽管算法B 的时间复杂度比C

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[25416,25525)) - 结论依据:原文由纳秒统计转向单位操作计数,保留模型前提而不承诺全部操作等价。 - 原始内容:计算操作运行时间统计”简化为“计算操作数量统计” ,这样一来估算难度就大大降低了。 ‧ 时间复杂度也存在一定的局限性。例如,尽管算法A C 的时间复杂度相同,但实际运行时间差别很 大。同样,尽管算法B 的时间复杂度比C