ループエンドは、無限大がゼロに近づくと終了しますか？

Question

私は次の問題の時間の複雑さを考えていました。正しい解決策はそれがO（logN）だと言います。私はこのループが終了する場合、これを理解しています。しかし私たちは半分しかないので、理論的には私は本当に0に近づくことができますが、決して終わらないでしょうか？

Answer 1

はい、ループは実際に終了します。 iはintなので、iを半分にすると、整数除算が実行されます。この除算の結果は、最も近い整数に切り下げられます。

int i=3; 
int j= i/2; 
// j really is 1.5, but we're performing integer division 
// so the result will be j =1 

私たちはN=5のためのあなたのプログラムの実行を考えると、私たちは持っている：

最初の反復：

i=5; 
i = i/2 = 5/2 = 2.5 = 2; //Round 2.5 down 

2回目の反復：

i=2 
i = i/2 = 2/2 = 1; 

サード例えば 繰り返し：

Answer 2

浮動小数点値ではなく、intを除算していることに留意することが重要です。したがって、分数コンポーネントはありません。代わりに、残りの部分は単に破棄されます。したがって、1になると0.5になり、整数の部分だけを取るので、0になります。したがって、これは最終的に終了します。例えば

、あなたは10を開始した場合：

10/2は1 -remainderの残りの部分と5

5/2ある2あるiが2

2/2されているdiscarded-ある1

1/2あなたは整数演算を使用しているdiscarded- iが0

Answer 3

ですので1 -remainderの残りの部分で0ですが、私はここでpicoc

$ picoc -i 
starting picoc v2.1 
picoc> #include <stdio.h> 
#include <stdio.h> 
picoc> int a=0, i=10; 
int a=0, i=10; 
picoc> a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a=10 i=5 
picoc> a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a=15 i=2 
picoc> a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a=17 i=1 
picoc> a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a += i; i /= 2; printf("a=%d i=%d\n",a,i); 
a=18 i=0 

あなたのループを使用してインタラクティブな例です0 に行くんこの時点で終了しました。