0

以下のコードブロックの実行時間O（n）を見つけようとしています。

int z=0;
int x=0; 
for (int i=1; i<=n; i=i*3){ //runs from 1->n, 1, 3, 9, 27... <- fcn that defines this?
   //constant running times below
   z = z+5;
   z++;
   x = 2*x;
}

i = i * 2の場合、実行時間はlognの複雑さになります。この場合はどうなりますか？

ティア。

4

2 に答える 2

1

nが15だったとしましょう。その場合、ループは次のようになります-

1、3、9 = 3回反復回数はlog_3（15）です。

一般に、入力を3分の1（または任意の分数）で半分または除算し、0まで上げる場合、それは除算するその係数の対数ベースになります。

半分にするとlog_2（n）になり、3分の1に割るとlog_3（n）になります。一般的な考え方がお役に立てば幸いです

于 2013-02-10T01:28:00.337 に答える
0

log_3（n）= log_2（n）/ log_2（3）であることに注意してください。ここで、log_2は基数2の対数を意味し、log_3は基数3の対数を意味します。したがって、log_2（n）はlog_3（n）に定数を掛けたものになります。

したがって、大きなOの定義によれば、実行時間がO（log_3（n））のコードもO（log（n））です。

于 2012-06-20T01:44:30.403 に答える