如何计算我的 C 函数的时间复杂度

Question

我写了一个函数来计算一个十进制数在二进制中的个数。如果输入是 3 那么它的二进制将是 0011 并且它应该将输出打印为两个。因为二进制中有两个1 number.How 我可以计算这个函数的时间复杂度吗？

    #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()的时间复杂度是O(log(n))（其中n是输入的数字）。

该数字以二进制表示，因此有 log_2(n) 位表示它。您的算法正在迭代所有这些位。
但是，请注意，要真正实现 O(logn) 时间复杂度，您应该在 n==0 时添加条件 break （以避免对已经为 0 的数字进行冗余迭代） .

---

从技术角度来看，整数由常数位数表示，如果您确实将此大小称为常数 - 算法 运行 时间是 O(1)，因为迭代次数有限，并且对所需的迭代次数有硬性限制。