我不知道这是否是正确的提问地点，因为我的问题是关于如何使用微分方程增长和衰减方法来计算计算机科学算法的复杂性。
我想证明的算法是对已排序数组的二分查找，其复杂度为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))，这当然是不正确的。
这种微分方程方法称为增长和衰减，非常流行。所以我想知道这种方法是否可以像我选择的那样应用于计算机科学算法，如果可以，我做错了什么而得到了不正确的线性搜索结果？谢谢
最佳答案
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)顺序结果!
关于algorithm - 微分方程 VS 算法复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24092792/