知识卡片
基本操作计数需要成本模型
复杂度分析先约定什么算作基本操作,再统计它随输入规模执行多少次。省略固定系数和低阶项后,可以得到更容易比较的渐近增长描述。
这不表示真实机器上加法、打印和任意长字符串操作耗时相同。把它们都当单位成本只适合明确的简化模型;若某项操作本身随数据长度增长,就要把这部分成本算入循环体。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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