再帰関数の時間複雑度（big O）はどのくらいですか？

Question

再帰関数には時間的複雑さがありますか？ ループ 'n'時間であるループは、forループの時間複雑さと同様にBig O（n）です。 同様に、再帰関数は固定された時間の複雑さを持つか、問題に依存します。また

Answer 1

、このような再帰関数：

func linear(n): 
    return (n <= 1) ? 1 : n * linear(n-1) 

は、複雑性O（N）を有します。

しかし

func exponential(n): 
    if n <= 1: return 1 
    exponential(n-1) 
    exponential(n-1) 

この例の後にあなたは本当の複雑さはO（2^n）のあなたはmaster theoremを使用することができます

---

This graph image would make more clear

Answer 2

ですが、それは、2N低下すると考えることができます。これは、再帰関数の時間の複雑さを判断するのに役立ちます。