← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1958.c.12.a.1.nu · 生成模型:未记录

增长阶与分析情形应分开

理解等级:中级

大O给出随输入规模增长的渐近上界,最坏、平均或均摊是分析对象的不同选择,不由符号本身强制决定。忽略低阶与常数有助于理解增长,但不能据此直接回答小输入哪段代码最快。表中O(n log n)误标为对数,应与O(log n)区分,输入规模也需明确如何计量。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《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中有多少