知识卡片
增长上界不能直接推出耗时
大O给出渐近增长上界,不包含常数,也不天然等于最坏情境或精确时间公式。读者校正:即便额外假设T(n)=c·log(n),从100到1000的比值也是1.5;若T(n)=c·n·log(n),比值是15,不能照抄原文3秒和33秒的推算。实际输入、常数和系统成本仍须测量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 39 算法速度 · 查看原书依据
大 O永远不会告诉你时间、内存或其他什么资源的真正开销数值:它只是告诉你数值会怎样跟着输入的量而变化。 第212页的图3——各种算法的运行时间,展示了几种常见的 O()符号给人的印象,这张图分类比较了它们各自的运行时间。
参考来源
- 位置:《程序员修炼之道:通向务实的最高境界(第2版)》,`extracted/程序员修炼之道:通向务实的最高境界(第2版)/_epub-src/text/part0016_split_003.html`。
- 结论依据:本处实际展开的论点与例证;正文中的读者边界分析不冒充原书已提供的实现。
- 原始内容:大 O永远不会告诉你时间、内存或其他什么资源的真正开销数值:它只是告诉你数值会怎样跟着输入的量而变化。 第212页的图3——各种算法的运行时间,展示了几种常见的 O()符号给人的印象,这张图分类比较了它们各自的运行时间。