小编Est*_*tex的帖子

Big-O 在算法阶的正式定义中常数 k 和 n0 是什么?

在我的教科书中,我看到以下内容:

定义算法的阶

算法 A 是 f(n) 阶——表示为 O(f(n))——如果常数 k 和 n 0存在使得 A 需要不超过 k * f(n) 个时间单位来解决大小为 n > = n 0


我理解:不同复杂性类别的时间要求以不同的速度增长。例如,随着 n 值的增加,O(n) 所需的时间增长比 O(n 2 ) 慢得多,后者比 O(n 3 )增长慢得多,依此类推。

我不明白: k 和 n 0如何符合这个定义。

  1. 什么是 n 0?具体来说,为什么n有下标0,这个下标是什么意思?

  2. 回答问题 1 后,“大小为 n >= n 0 的问题”是什么意思?更大的数据集?更多的循环重复?问题规模越来越大?

  3. 那什么是k呢?为什么 k 乘以 f(n)?k 与增加问题规模 - n 有什么关系?

我已经看过了:

  1. Big Oh Notation - 正式定义

  2. Big O 正式定义中的常量

  3. 在证明算法的大哦时找到 C 和 N 的简单方法是什么?

  4. 如果 f(x) …

algorithm performance big-o notation

6
推荐指数
1
解决办法
2365
查看次数

标签 统计

algorithm ×1

big-o ×1

notation ×1

performance ×1