知识卡片
复杂度描述输入增长趋势
大 O 用来描述输入规模增大时工作量的增长界,不是某次运行耗时。O(n) 与 O(n²) 的比较需要明确 n 以及一次基本操作的成本;小输入时常数和实际布局仍可能主导。哈希表的常数时间通常带有分布等前提;算法复杂度也没有原文所称的 O(n!) 这一通用最差上限。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.2 算法复杂度 · 查看原书依据
中通常用大O表示法来描述算法的复杂度。因此,只需要访问线性次输入数据的O(n)算法要更优于O(n2)的算法以及O(n3)的算法等等。然而最坏的算法就是O(n!),想输入超过300个元素是不可能的。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.2 算法复杂度,spine080(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.2.html)。
- 结论依据:原文用多种增长率比较算法,并把内置结构作例;保留增长模型,纠正过度概括。
- 原始内容:中通常用大O表示法来描述算法的复杂度。因此,只需要访问线性次输入数据的O(n)算法要更优于O(n2)的算法以及O(n3)的算法等等。然而最坏的算法就是O(n!),想输入超过300个元素是不可能的。