知识卡片
增长阶由规模变化方式决定
固定次数与输入大小无关,是常数增长;扫描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