知识卡片
增长阶与分析情形应分开
大O给出随输入规模增长的渐近上界,最坏、平均或均摊是分析对象的不同选择,不由符号本身强制决定。忽略低阶与常数有助于理解增长,但不能据此直接回答小输入哪段代码最快。表中O(n log n)误标为对数,应与O(log n)区分,输入规模也需明确如何计量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 优化——一些强大的技术 12.1.2 大O记法 · 查看原书依据
O(n log n) 对数
参考来源
- 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第12章 优化——一些强大的技术,spine021单元004;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00020.html。
- 结论依据:原文复杂度表及O(n log n)误标,对照增长定义可区分渐近上界与平均/最坏情形,不用标签直接判断小输入速度。未在本机运行示例或改变环境。
- 原始内容:输入的数据 O(n) 线性。按照n增长 O(n log n) 对数 O(n 2 ) 平方复杂度 O(n 3 ) 立方复杂度 O(n!) 阶乘复杂度 例如,在第2章中已经讲过,在字典中查找的平均复杂度为 O(1) 。不管在dict中有多少