我编写了一个函数来计算十进制数字的二进制数。如果输入为3，则其二进制数将为0011，并且应将输出打印为两个。由于二进制数中有两个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);
}
从纯算法角度讲，时间复杂度numberof_1()为O(log(n))（其中n输入数字为）。
该数字以二进制为单位表示，因此具有log_2(n)表示它的位。您的算法正在迭代所有这些位。
但是，请注意，要真正实现这一目标O(logn)的时间复杂度，你应该添加一个条件break时n==0（以避免一些这已经是0冗余迭代）。
从技术角度来看，整数是用恒定位数表示的，并且如果您确实将此大小称为常数，则算法运行时间为O(1)，因为迭代次数是有限的，并且迭代次数有一定的限制需要。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句