如何计算以下等式的大 O 符号？
How to calculate the Big O notation of following equations?
- 这是一个递归公式：
E(r,n) = (E(r-1,n-1)-E(r,n-1))^2 + E(r,n-1) r<=n
也请展示获得Big O的过程。
- 从 i=0 到 r 的求和，(r-i)(n 选择 i)(p^(n-i) * (1-p)^i)
我认为计算这个等式的大 O 等于计算大 O：
从 i=0 到 r 的求和，（n 选择 i）
这是正确的吗？
也请展示获得大O的过程
假定我对问题的理解是正确的，并且您想要一个执行这些操作的程序的时间复杂度：
该递归的基本情况是什么？假设 E(0,0) 是基本情况，E(r,0) 是线性递归，直到 E(0,0) 和 r > n。想象一下，我们形成了一个递归树。我们会得到，每一层都会用上一层的 n 减一来调用函数，因为函数总是用 n-1 调用自己。现在分析树并将其分离我们得到：
- 三重递归直到 n = 0；
- n = 0后，我们得到一个线性递归的分支（a依赖于n和r）
分析三重递归，我们可以通过各种方法（生成函数，硕士等）发现它的复杂性，但让我们使用更简单的方法。假设每个节点使用一个时间单位。我们知道每一层有前一层节点的3倍，第一层有一个节点，树有n层，总时间是所有节点的总和。所以我们明白了
TotalTripleTime = Summ(0, n) of 3^k
这可以通过几何级数的封闭公式给出，因此：
(1-3^n+1)/-2 即 O(3^n)
由于递归比较复杂，所以计算起来有点困难，我也没有很多时间，也许我以后再试试。
- 假设 r 小于 n，我们简单地得到 O(r * O(combinatations)) 假设使用闭合公式计算一个简单的组合是 O(n)，我们得到 O(n* r).
- 这是一个递归公式：
E(r,n) = (E(r-1,n-1)-E(r,n-1))^2 + E(r,n-1) r<=n
也请展示获得Big O的过程。
- 从 i=0 到 r 的求和，(r-i)(n 选择 i)(p^(n-i) * (1-p)^i)
我认为计算这个等式的大 O 等于计算大 O：
从 i=0 到 r 的求和，（n 选择 i）
这是正确的吗？
也请展示获得大O的过程
假定我对问题的理解是正确的，并且您想要一个执行这些操作的程序的时间复杂度：
该递归的基本情况是什么？假设 E(0,0) 是基本情况，E(r,0) 是线性递归，直到 E(0,0) 和 r > n。想象一下，我们形成了一个递归树。我们会得到，每一层都会用上一层的 n 减一来调用函数，因为函数总是用 n-1 调用自己。现在分析树并将其分离我们得到：
- 三重递归直到 n = 0；
- n = 0后，我们得到一个线性递归的分支（a依赖于n和r）
分析三重递归，我们可以通过各种方法（生成函数，硕士等）发现它的复杂性，但让我们使用更简单的方法。假设每个节点使用一个时间单位。我们知道每一层有前一层节点的3倍，第一层有一个节点，树有n层，总时间是所有节点的总和。所以我们明白了 TotalTripleTime = Summ(0, n) of 3^k 这可以通过几何级数的封闭公式给出，因此： (1-3^n+1)/-2 即 O(3^n)
由于递归比较复杂，所以计算起来有点困难，我也没有很多时间，也许我以后再试试。
- 假设 r 小于 n，我们简单地得到 O(r * O(combinatations)) 假设使用闭合公式计算一个简单的组合是 O(n)，我们得到 O(n* r).