请问：判断n位数1的个数的时间复杂度是多少，为什么，多谢

请教：判断n位数1的个数的时间复杂度是多少，为什么，谢谢

C/C++ code

int NumberOfOne(int num)
{
   int count =0;
   while(num)
   {
    if(num%10==1)count++;
   num/=10;
   }
  return count;
}

------解决方案--------------------
一般而言，一个算法的执行时间的求解问题的规模n的函数，这是因为问题的规模往往决定了算法工作量的大小。但是，我们不关心它是个怎样的函数，只关心它的数量级量度，及它与什么简单函数f（n）是同一个数量级的。
常见的时间复杂度，按数量级递增排序有：常数阶O（1）、线性阶O（n）、平方阶O（n2）、立方阶O（n3）等
其中O是数学符号
而你的这个程序的问题规模明显就是数的位数n，故时间复杂度为O（n）
------解决方案--------------------

探讨

C/C++ code

int NumberOfOne(int num)
{
int count =0;
while(num)
{
if(num%10==1)count++;
num/=10;
}
return count;
}

------解决方案--------------------

探讨

看输入。
对于一个int。
完全可以做到logn

------解决方案--------------------
用容斥原理最简单，没有之一。。

参见这个题目：http://sznoi.cn/oj/ShowProblem?problemid=m005