从图中确定渐近增长率

Question

我正在尝试确定下图的渐近增长率，它具有对数 x-axis（基数 2）和线性 y-axis。在我看来 sub-logarithmic，但是如何准确确定速率（在渐近复杂度的 big-O 表示法中）？上图原图，蓝线下方是sqrt()，绿色是log()，最后一个是原函数

Answer 1

假设你可以展示一个常数 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 将是 "close" 到 平方根 函数。

免责声明： 请格外小心这里的 "close"，因为渐进地，x^(0.5 +/- epsilon) 因为 epsilon > 0 与 sqrt(x) 相去甚远（我的意思是 - 两个函数之间的区别可以任意大 x -> +Inf).

从图中确定渐近增长率

Determine asymptotic growth rate from plot

plot

big-o

asymptotic-complexity