algorithm - 微分方程 VS 算法复杂度

Question

我不知道问这个地方是否合适，因为我的问题是关于如何使用微分方程增长和衰减方法计算计算机科学算法的复杂性。

我想证明的算法是二分查找排序数组，其复杂度为log2(n)

算法说:如果要搜索的目标值等于中间元素，则返回它的索引。如果小于，则在左子数组上搜索，如果更大，则在右子数组上搜索。

如您所见，每次 N(t):[时间 t 的节点数] 除以一半。因此，我们可以说找到一个元素需要 O(log2(n))。

现采用微分方程增长衰减法。

dN(t)/dt = N(t)/2 

dN(t):元素数量增加或减少的速度有多快
dt: 相对于时间
N(t):时间t的元素个数

上面的等式表示细胞数随时间除以 2。

求解上述方程得到:

dN(t)/N(t) = dt/2
ln(N(t)) = t/2 + c
t = ln(N(t))*2 + d

即使我们得到的是 t = ln(N(t)) 而不是 log2(N(t))，我们仍然可以说它是对数的。

不幸的是，上面的方法，即使在接近它来寻找二分搜索复杂度时是有意义的，结果证明它并不适用于所有算法。这是一个反例:

线性搜索数组:O(n)

dN(t)/dt = N(t)
dN(t)/N(t) = dt
t = ln(N(t)) + d

所以根据这种方法，线性搜索的复杂度为 O(ln(n))，这当然不是真的。

这种微分方程法叫做增长和衰减，非常流行。所以我想知道这种方法是否可以像我选择的那样应用于计算机科学算法，如果可以，我做错了什么以获得线性搜索的错误结果？谢谢

Answer 1

The time an algorithm takes to execute is proportional to the number of steps covered(reduced here).

在数组的线性搜索中，您假设 dN(t)/dt = N(t)。

不正确的假设:-

dN(t)/dt = N(t)
dN(t)/N(t) = dt
t = ln(N(t)) + d

按照您之前的假设，二分搜索将因子减少 1/2 项(在数组遍历的每次遍历中直接减少半项遍历，从而减少搜索项的数量一半)。所以，您的 dN(t)/dt=N(t)/2 观点很好。但是，当您谈论线性搜索数组时，很明显，您是在一次访问中访问元素，因此，您的搜索词在每次访问中都按一个项目的顺序递减。那么，您的假设怎么会成立呢？？？

正确假设:-

dN(t)/dt = 1
dN(t)/1 = dt
t = N(t) + d

希望您明白我的意思。每个数组元素都按顺序访问一次(迭代)。所以，数组访问不是按照N(t)的顺序变化的，而是按照常数1的顺序变化的。所以，这个N(T)顺序的结果!