知识卡片

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

增长阶由规模变化方式决定

理解等级:中级

固定次数与输入大小无关,是常数增长;扫描n个元素通常是线性;每个元素再比较其余候选,可能得到平方数量。三者描述规模增大后的工作变化,不是运行时间的绝对排名。

每轮工作量翻倍会积累指数数量,而每轮把剩余规模按固定比例缩小,只需对数轮数。分析前还要确定n指元素数量、数值大小还是编码长度,不能把不同口径直接比较。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      常数阶的操作数量与输入数据大小 无关,即不随着 的变化而变化。 在以下函数中,尽管操作数量size 可能很大,但由于其与输入数据大小 无关,因此时间复杂度仍为 : // === File: time_complexity

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[27388,27498)) - 结论依据:原文常数/线性/平方、指数细胞与对数折半代码实际展开,用同一规模变化关系归组。 - 原始内容:常数阶的操作数量与输入数据大小 无关,即不随着 的变化而变化。 在以下函数中,尽管操作数量size 可能很大,但由于其与输入数据大小 无关,因此时间复杂度仍为 : // === File: time_complexity