は

Question

私はアルゴリズムに従ってた発声しますこのチルダ関数でアルゴリズムの複雑さを分けるとき、無限の限界は1でなければなりません。

私は正確な複雑さを計算する必要はないと思っています。私たちはチルダ - 複雑さを持っています。

インデックスoff成長を見ることによって、私はこのアルゴリズムは

~ log N 

むしろバイナリ対数関数を持つよりも、あると仮定し、この場合、ベースは正確なため、この問題3. んです表記法？成長の順序はまったく同じですか？したがって、Tilde表記を使用する場合、ベースを無視できますか？私はこれに正しくアプローチしていますか？

Answer 1

正しいですが、forループはceil(log_3 N)回実行されます。log_3 Nは、基数3の対数であるNを表します。

いいえ、チルダ表記を使用している場合は、ベースを無視できません。

ここで、時間の複雑さをどのように引き出すことができるかを示します。 forループの各反復は、Cの値を、ある一定の値のためにはC>0と仮定します。

T(N)は、forループの実行回数を示します。 j番目の反復では、iの値は3^jであるため、私たちが行う反復回数はjのうち、の最小値になります。両側の底3対数を取ると、j >= log_3 Nが得られます。 jは整数であるため、j = ceil(log_3 N)です。従ってT(N) ~ ceil(log_3 N)。

S(N)は、forループの時間複雑度を示します。従って、「合計」時間の複雑さは、T(N)反復のそれぞれのコストがCであり、チルド記号でS(N) ~ C * ceil*(log_3 N)と書くことができるので、C * T(N)である。