两个简单的递归函数大O符号 [英] Big-O notation for two simple recursive functions

问题描述

我在Python两个递归函数和单纯只是想知道大O符号为他们。什么是大O为每一个？

 高清费用（N）：
    如果n == 0：
        返回1
    其他：
        返回成本（N-1）+成本（N-1）

高清费用（N）：
    如果n == 0：
        返回1
    其他：
        返回2 *成本（N-1）
 

解决方案

让我们用递推关系来解决这个问题！第一个函数的运行时间可以递归描述为

  

T（0）= 1

     

T（N + 1）= 2T（正）+1

也就是说，基本情况需要一个时间单位来完成，否则我们做两个递归调用问题较小的实例，做的设置和清理工作的一些数额。扩大了一些术语在此再次发生，我们得到

• T（0）= 1
• T（1）= 2T（0）+ 1 = 2 + 1 = 3
• T（2）= 2T（1）+ 1 = 2＆倍; 3 + 1 = 7
• T（3）= 2T（2）+ 1 = 2＆倍; 7 + 1 = 15

这系列1，3，7，15，...可能看起来很熟悉，因为它是2 ¹ - 1，2 ² - 1，2 ³ - 1等更一般地，我们可以证明

  

T（N）= 2 ^{N + 1} - 1

我们可以通过归纳做到这一点。由于我们的基本情况，T（0）= 1 = 2 ¹ - 1，因此声称拥有对n = 0。现在假设，对于一些n表示T（N）= 2 ^{ñ +1} - 1。然后我们有一个

  

T（N + 1）= 2T（n）的+ 1 = 2（2 ^{n + 1个} - 1）+ 1 = 2 ^{n + 2中} - 2 + 1 = 2 ^{N + 2} - 1

和我们就大功告成了！由于这种复发工程以2 ^{n + 1个} - 1 = 2（2 ^N ） - 1，我们有运行时是＆西塔;（2 ^N ）。

第二个函数的运行时可以递归描述为

  

T（0）= 1

     

T（N + 1）= T（N）+1

扩大了一些术语：

• T（0）= 1
• T（1）= T（0）+ 1 = 1 + 1 = 2
• T（2）= T（1）+ 1 = 2 + 1 = 3
• T（3）= T（2）+ 1 = 3 + 1 = 4

这给了1，2，3，4，...，所以更普遍，我们可以猜测

  

T（N）= N + 1

我们可以归纳再次证明了这一点。作为碱的情况下，如果n = 0，则T（0）= 1 = 0 + 1。归纳步骤，假设对于某些n表示T（N）= N + 1。然后

  

T（N + 1）= T（N）+ 1 = N + 1 + 1 = n + 2中

和我们就大功告成了！由于运行时间为n + 1，运行时间是与西塔;（N）

希望这有助于！

I have two recursive functions in Python and simply just want to know the Big O Notation for them. What is the Big O for each these?

def cost(n):
    if n == 0:
        return 1
    else:
        return cost(n-1) + cost(n-1)

def cost(n):
    if n == 0:
        return 1
    else:
        return 2*cost(n-1)

解决方案

Let's use recurrence relations to solve this! The first function's runtime can be described recursively as

T(0) = 1

T(n + 1) = 2T(n) + 1

That is, the base case takes one time unit to complete, and otherwise we make two recursive calls to smaller instances of the problem and do some amount of setup and cleanup work. Expanding out some terms in this recurrence, we get

• T(0) = 1
• T(1) = 2T(0) + 1 = 2 + 1 = 3
• T(2) = 2T(1) + 1 = 2 × 3 + 1 = 7
• T(3) = 2T(2) + 1 = 2 × 7 + 1 = 15

This series 1, 3, 7, 15, ... might look familiar, since it's 2¹ - 1, 2² - 1, 2³ - 1, etc. More generally, we can prove that

T(n) = 2ⁿ⁺¹ - 1

We can do this by induction. As our base case, T(0) = 1 = 2¹ - 1, so the claim holds for n = 0. Now assume that for some n that T(n) = 2ⁿ⁺¹ - 1. Then we have that

T(n + 1) = 2T(n) + 1 = 2(2ⁿ⁺¹ - 1) + 1 = 2ⁿ⁺² - 2 + 1 = 2ⁿ⁺² - 1

And we're done! Since this recurrence works out to 2ⁿ⁺¹ - 1 = 2(2ⁿ) - 1, we have that the runtime is Θ(2ⁿ).

The second function's runtime can be described recursively as

T(0) = 1

T(n + 1) = T(n) + 1

Expanding out some terms:

• T(0) = 1
• T(1) = T(0) + 1 = 1 + 1 = 2
• T(2) = T(1) + 1 = 2 + 1 = 3
• T(3) = T(2) + 1 = 3 + 1 = 4

This gives 1, 2, 3, 4, ..., so more generally we might guess that

T(n) = n + 1

We can prove this inductively again. As a base case, if n = 0, then T(0) = 1 = 0 + 1. For the inductive step, assume that for some n that T(n) = n + 1. Then

T(n + 1) = T(n) + 1 = n + 1 + 1 = n + 2

And we're done! Since the runtime is n + 1, the runtime is Θ(n).

Hope this helps!

这篇关于两个简单的递归函数大O符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！