runtime - ブロック コードのランタイム

Question

このコードの実行時複雑度 T(n) が 2lgn+2 である理由を説明してください。私はそれがlgn + 2であるべきだと思った。

public static reduce(int n){
 int result = 0;
 while (n >1){
   n = n/2;
   result = result +1;
 }
 return result;
} 

Answer 1

おそらく、各行には1単位の時間がかかると想定されています（n > 1チェックは含まれていません）。

したがってint result = 0;、n = n/2;、 、result = result +1;およびreturn result;それぞれは、1 単位の時間がかかるものとして分類されます。

2 から来てint result = 0;、return result;それぞれが 1 回実行されます。

2 log ₂ n から来てn = n/2;、result = result +1;それぞれが log ₂ n 回実行されます。

ノート：

n > 1時間の単位として分類することもでき、結果として 3 log ₂ n + 2 になります。

n = n/2;そして、result = result +1;それぞれ 2 単位の時間がかかると分類でき、(上記の場合) 5 log ₂ n + 2 になります。

それはすべて非常に主観的です。

全体的な唯一の合意は、いくつかの c と d に対してclog _{2 n + d です。}