差分方程(递推关系)在IT领域的应用

Question

我现在正在做IT文凭和数学课程-- there.In，我们必须学习差分方程(递归关系)，我对这些概念在IT的不同领域的用法感到困惑，比如计算、算法和数据结构、电路分析等等。

有谁能解释一下为什么我们要学习这些概念及其用法吗？这将对我的学习有所帮助。

Answer 1

Unutbu有一个很好的解释和联系什么是重复关系。这是一个了解原因的小窗口。

计算机科学家需要知道算法是如何相互比较的(在速度或内存空间方面)。递归关系有助于提供这种比较(按数量级计算)。

这里有一个一般性的问题：国际象棋有几个可能的动作？，如果有3180亿个移动(前四个)，你能用一个详尽的算法来搜索最好的，第一步吗？如果这是不切实际的，那么有什么算法可以将其缩减到一个合理的大小呢？复杂性度量为我们提供了一个洞察问题的困难和一个给定算法的实用性。

Answer 2

复杂性理论中出现了递推关系。递归算法执行的步骤数可以表示为递归关系，例如

​

​

然后，我们的目标是将T表示为(或绑定T )一个(希望是简单的) n函数。

主定理就是这样做的一个例子。