再帰式の時間複雑さを見つける

Question

私は再帰式の時間複雑度（big O）を見つけようとしています。

Answer 1

Brenner氏によると、あなたの最後の仮定は偽です。 （n代わりxの使用）のがWikipedia pageからO(n)の定義を見てみましょう：

f(n) = O(n)場合と定数cが存在する場合にのみ、n0 S。T.ここ理由です|f(n)| <= c |g(n)|、すべてn >= n0です。

O(2^n^2) = O(2^n)を確認します。明らかに、2^n^2はO(2^n^2)にありますので、f(n) = 2^n^2を選択し、O(2^n)にあるかどうかを確認してください。上記の式にこれを入れて：我々はそれが真実でないことを証明する矛盾を導き出すことができれば、我々はn0とcそのために上記適した定数値を見つけることができるかどうか見てみましょう

exists c, n0: 2^n^2 <= c * 2^n for all n >= n0

ことは事実である、または：

両側にログを取る：

log(2^n^2) <= log(c * 2^n)

簡素化を：

log(2)によって

2 ^n log(2) <= log(c) + n * log(2)

デバイド：

n^2 <= log(c)/log(2) * n

cがないことを知って見ることは簡単です、上記のすべてのn >= n0についても同様ですn0いるが、これO(2^n^2) = O(n^2)は有効な仮定ではありません。

Answer 2

疑問符で指定した最後の仮定が偽である：

は、私はあなたが以下の式と私の解決策が表示されることがあり、解決策を見つけることを試みました！そのような前提をしないでください。

残りの操作は正しいと思われます。しかし、彼らは実際にあなたをどこにも連れません。

あなたのドラフトの途中でこの練習を終えておく必要があります。

T(n) = O(T(1)^(3^log2(n))) 

そして、それはそれです。それが解決策です！

あなたが実際にその

3^log2(n) == n^log2(3) ==~ n^1.585 

主張することができ、その後、あなたが得る：

T(n) = O(T(1)^(n^1.585)) 

あなたがドラフトの第二部で行った操作に少し似ています。 だから、このままにすることもできます。しかし、あなたは指数を混乱させることはできません。指数の値を変更すると、big-O分類が変更されます。