在我的教科书中,我看到以下内容:
定义算法的阶
算法 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如何符合这个定义。
什么是 n 0?具体来说,为什么n有下标0,这个下标是什么意思?
回答问题 1 后,“大小为 n >= n 0 的问题”是什么意思?更大的数据集?更多的循环重复?问题规模越来越大?
那什么是k呢?为什么 k 乘以 f(n)?k 与增加问题规模 - n 有什么关系?
我已经看过了: