从图中确定渐近增长率

在这个假设下,你可以展示一个常数 c 因此 f(2^(i+1))/f(2^i)) = c 对于每个整数 i ,您可以考虑以下事实:

f(2^i) = c.f(2^(i-1)) = c^i.f(1)

对于任何整数k,

f(k) = f(2^log2(k))
     = c^log2(k).f(1)
     = k^log2(c).f(1)

我试着估计了几个比率值 f(2^(i+1)) / f(2^i) :

f(2^12) / f(2^11) ~= 0.250 / 0.175 ~= 1.43
f(2^11) / f(2^10) ~= 0.175 / 0.125 ~= 1.4
f(2^10) / f(2^9)  ~= 0.125 / 0.085 ~= 1.47
f(2^9)  / f(2^8)  ~= 0.085 / 0.070 ~= 1.21

对于较低的 x 。

我不清楚你是否真的有一个恒定的比率 f(2^(i+1))/f(2^i) (您可能需要更多数据 x > 2^13 ),但是,例如,如果您选择采用 c = 1.4 ,您将得到函数 f(k)/f(1) ~= k^0.49 ~= sqrt(k) ,即。 1/f(1).f 将“接近” 平方根 作用

免责声明: 请在此处“关闭”时格外小心,因为渐近, x^(0.5 +/- epsilon )用于 epsilon > 0 只不过是遥远的 sqrt(x) (我的意思是-两个函数之间的差异可以任意大为 x -> +Inf )。