次のアルゴリズムがあるとします。
for(int i = 1; i < N; i *= 3) {
sum++
}
チルダ表記を使用して複雑さを計算する必要があります。これは基本的に、チルダ関数を見つけて、アルゴリズムの複雑さをこのチルダ関数で割ったときに無限大の限界が 1 になるようにする必要があることを意味します。
正確な複雑さを計算する必要はないと思います。定数を無視して、チルダの複雑さを得ることができます。
インデックスからの伸びを見ると、このアルゴリズムは
~ log N
しかし、2 進対数関数を使用するのではなく、この場合の底は 3 です。これは正確な表記に関係しますか? 成長の順序はまったく同じなので、チルダ表記を使用するときに基数を無視できますか? これに正しくアプローチできますか？
そうです、for ループはceil(log_3 N)回数を実行します。ここでlog_3 N、 の底 3 の対数を示しNます。
いいえ、チルダ表記を使用する場合、基数を無視することはできません。
時間の複雑さを導き出す方法は次のとおりです。for ループの各反復コストCは、ある定数に対してと仮定しますC>0。
forT(N)ループの実行回数を とします。j番目の反復で の値は でiあるため3^j、反復の回数が最小jになるのは、どの かということになり3^j >= Nます。両辺の 3 を底とする対数を取ると、 が得られj >= log_3 Nます。jは整数であるため、 j = ceil(log_3 N). したがってT(N) ~ ceil(log_3 N)。
forS(N)ループの時間計算量を とします。というのは、各反復C * T(N)のコストがであり、チルダ表記で と書くことができるからです。T(N)CS(N) ~ C * ceil*(log_3 N)