私のC関数の時間複雑度を計算する方法

Question

10進数のバイナリで1の数を計算する関数を書いた。入力が3の場合、バイナリは0011になり、出力は2として出力されます。バイナリ数には2つの1があるため、この関数の時間複雑度はどのように計算できますか？

#include<stdio.h> 
    void main() 
    { 
    void numberof_1(int n) 
     { 
     int i,count=0; 
     if ((n & 1)== 1) 
     count=count+1; 
     printf("%d",count); 
     for(i=0;i<32;i++) 
     { 
      n= n >> 1; 
      if ((n & 1)==1) 
      { 
       count=count+1; 
      } 
      } 
    printf("\nthe number of ones =%d\n",count); 

     } 
    numberof_1(10); 
    } 

Answer 1

ビューの純粋にアルゴリズムの点から言えば、numberof_1()の時間複雑度は、（n入力数である）O(log(n))あります。

この数値は、2進数で表され、したがって、それを表すlog_2(n)ビットを持ちます。あなたのアルゴリズムはこれらすべてのビットを反復しています。
しかし、実際にはO(logn)時間の複雑さを達成するには、n==0の場合は、条件付きbreakを追加する必要があります（既に0の数字に冗長な繰り返しを避けるため）。技術的な観点からは

---

は、整数は確かにビットの定数数で表され、あなたがこのサイズを参照している場合など、一定している - 繰り返しの回数が制限されており、そこにあるようなアルゴリズムの実行時間は、O(1)です必要な反復の数にハードバインドされています。