算法的时间复杂度是如何减少的
服务器君一共花费了22.672 ms进行了2次数据库查询，努力地为您提供了这个页面。
试试阅读模式？希望听取您的建议
给定一个十进制整数N，求出从1到N的所有整数中出现"1"的个数。
例如：N=2，1,2出现了1个"1"。
N=12，1,2,3,4,5,6,7,8,9,10,11,12。出现了5个"1"。
最直接的方法就是从1开始遍历到N，将其中每一个数中含有"1"的个数加起来，就得到了问题的解。
public long CountOne3(long n)
long i = 0,j = 1;
long count = 0;
for (i = 0; i &= i++)
while (j != 0)
if (j % 10 == 1)
j = j / 10;
此方法简单，容易理解，但它的问题是效率，时间复杂度为O（N * lgN），N比较大的时候，需要耗费很长的时间。
我们重新分析下这个问题，对于任意一个个位数n，只要n>=1,它就包含一个"1"；n&1，即n=0时，则包含的"1"的个数为0。于是我们考虑用分治的思想将任意一个n位数不断缩小规模分解成许多个个位数，这样求解就很方便。
但是，我们该如何降低规模？仔细分析，我们会发现，任意一个n位数中"1"的个位可以分解为两个n-1位数中"1"的个数的和加上一个与最高位数相关的常数C。例如，f(12) = f(10 - 1) + f(12 - 10) + 3,其中3是表示最高位为1的数字个数，这里就是10,11,12；f(132)=f(100 -1) + f(132 - 100) + 33，33代表最高位为1的数字的个数，这里就是100~132；f(232) = 2*f(100 - 1) + f(32) + 100，因为232大于199，所以它包括了所有最高位为1的数字即100~199，共100个。
综上，我们分析得出，最后加的常数C只跟最高位n1是否为1有关，当最高位为1时，常数C为原数字N去掉最高位后剩下的数字+1，当最高位为1时，常数C为10bit，其中bit为N的位数-1，如N=12时，bit=1，N=232时，bit=2。
于是，我们可以列出递归方程如下：
if(n1 == 1)
f(n) = f(10bit-1) + f(n - 10bit)
+ n - 10bit+ 1;
f(n) = n1*f(10bit-1) + f(n – n1*10bit) + 10bit;
递归的出口条件为：
if(1&n&10)
else if (n == 0) return 0;
基于此，编写如下代码：
public long CountOne(long n)
long count = 0;
if (n == 0)
count = 0;
else if (n > 1 && n & 10)
long highest =//表示最高位的数字
int bit = 0;
while (highest >= 10)
highest = highest / 10;
int weight = (int)Math.Pow(10, bit);//代表最高位的权重，即最高位一个1代表的大小
if (highest == 1)
count = CountOne(weight - 1)
+ CountOne(n - weight)
+ n - weight + 1;
count = highest * CountOne(weight - 1)
+ CountOne(n - highest * weight)
此算法的优点是不用遍历1~N就可以得到f(N)。经过我测试，此算法的运算速度比解法一快了许多许多，数字在1010内时，算法都可以在毫秒级内结束，而解法一在计算109时，时间超过了5分钟。但此算法有一个显著的缺点就是当数字超过1010时会导致堆栈溢出，无法计算。
还有就是，我尝试了许久也没有计算出此算法的时间复杂度到底是多少，似乎是O（lg2N），我并不确定，希望知道的高手能给予解答。
解法二告诉我们1~ N中"1"的个数跟最高位有关，那我们换个角度思考，给定一个N，我们分析1~N中的数在每一位上出现1的次数的和，看看每一位上"1"出现的个数的和由什么决定。
1位数的情况：在解法二中已经分析过，大于等于1的时候，有1个，小于1就没有。
2位数的情况：N=13,个位数出现的1的次数为2，分别为1和11，十位数出现1的次数为4，分别为10,11,12,13，所以f(N) = 2+4。N=23,个位数出现的1的次数为3，分别为1，11，21，十位数出现1的次数为10，分别为10~19，f(N)=3+10。
由此我们发现，个位数出现1的次数不仅和个位数有关，和十位数也有关，如果个位数大于等于1，则个位数出现1的次数为十位数的数字加1；如果个位数为0，个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关，也和个位数相关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，假如十位数大于1，则十位数上出现1的次数为10。
3位数的情况：
N=123，个位出现1的个数为13:1,11,21，…，91,101,111,121。十位出现1的个数为20:10~19,110~119。百位出现1的个数为24:100~123。
我们可以继续分析4位数，5位数，推导出下面一般情况： 假设N，我们要计算百位上出现1的次数，将由三部分决定：百位上的数字，百位以上的数字，百位一下的数字。
如果百位上的数字为0，则百位上出现1的次数仅由更高位决定，比如12013，百位出现1的情况为100~199,00~2199，…，，共1200个。等于更高位数字乘以当前位数，即12 * 100。
如果百位上的数字大于1，则百位上出现1的次数仅由更高位决定，比如12213，百位出现1的情况为100~199,00~2199，…，，共1300个。等于更高位数字加1乘以当前位数，即（12 + 1）*100。
如果百位上的数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。例如12113，受高位影响出现1的情况：100~199,00~2199，…，，共1200个，但它还受低位影响，出现1的情况是，共114个，等于低位数字113+1。
综合以上分析，写出如下代码：
public long CountOne2(long n)
long count = 0;
long i = 1;
long current = 0,after = 0,before = 0;
while((n / i) != 0)
current = (n / i) % 10;
before = n / (i * 10);
after = n - (n / i) *
if (current > 1)
count = count + (before + 1) *
else if (current == 0)
count = count + before *
else if(current == 1)
count = count + before * i + after + 1;
i = i * 10;
此算法的时间复杂度仅为O(lgN)，且没有递归保存现场的消耗和堆栈溢出的问题。
本文地址：，欢迎访问原出处。
不打个分吗？
转载随意，但请带上本文地址：
如果你认为这篇文章值得更多人阅读，欢迎使用下面的分享功能。
小提示：您可以按快捷键 Ctrl + D，或点此 。
大家都在看
现代魔法研究协会欢迎你
阅读一百本计算机著作吧，少年
程杰 (作者)
《大话数据结构》主要内容包含：数据结构介绍、算法推导大O阶的方法；顺序结构与链式结构差异、栈与队列的应用；串的朴素模式匹配、KMP模式匹配算法；二叉树前中后序遍历、赫夫曼树及应用；图的深度、广度遍历；最小生成树两种算法、最短路径两种算法；拓扑排序与关键路径算法；折半查找、插值查找、斐波那契查找等静态查找；稠密索引、分块索引、倒排索引等索引技术；二叉排序树、平衡二叉树等动态查找；B树、B+树技术，散列表技术；冒泡、选择、插入等简单排序；希尔、堆、归并、快速等改进排序。
扫一扫，在手机上阅读
栏目最新博文
11,087 views
7,512 views
7,528 views
7,868 views
7,371 views
9,500 views
5,945 views
5,723 views
7,032 views
6,770 views
栏目博文推荐
5,723 views
2,091 views
4,031 views
2,880 views
3,431 views
7,371 views
3,356 views
3,753 views
5,814 views
6,214 views
今天的努力决定未来的成败。
1,562 views
关于网站与作者
互联网信息太多太杂，各互联网公司不断推送娱乐花边新闻，SNS，微博不断转移我们的注意力。但是，我们的时间和精力却是有限的。这里是互联网浩瀚的海洋中的一座宁静与美丽的小岛，供开发者歇息与静心潜心修炼（愿景）。
“Veda”的本义是知识、启示，希望这里能为开发者提供充足的技术资料。
我的电子邮件gonnsai(，腾讯微博：，欢迎与我联系。根号1加根号2加根号3加到根号n加相加是多少_百度作业帮
根号1加根号2加根号3加到根号n加相加是多少
1加根号2 分之1 加根号二加根号三 分之1加到根号n加跟号n 1分之一1/(1 根号2) 1/(根2 根3) …… 1/(根n 根（n 1）)=（1-根2）/[(1 根号2)(1-根2) ] （根2-根3）/[(根2 根3)根2 根3] …… (根n 根（n 1）)/[(根n 根（n 1）)(根n-根（n 1）)]=（1-根2）/(1-2) （根2-根3）/(2-3) …… (根n 根（n 1）)/(n-n-1)=根2-1 根3-根2 …… 根（n 1）-根n注意到根2 和负根2 抵消,同样根3和后面的美写出的负3抵消……根n和负根n抵消最终结果为根（n 1）-1
您可能关注的推广n乘（n加1）分之1等于几1—— = 等于多少n(n+1)_百度作业帮
n乘（n加1）分之1等于几1—— = 等于多少n(n+1)
n乘（n加1）分之1等于1除以n乘（n加1）2的3次方 加 2的4次方 加 2的5次方 一直加到2的n加1次方 等于多少
2的3次方 加 2的4次方 加 2的5次方 一直加到2的n加1次方 等于多少
手机躺在床上，你自己用公式算算，前面加2的平方，公比为2，n为n，公式一用，最后减4，你还不会啊！
要的就是这个答案. 因为不知道是多少.所以算不了. 谢谢
因为不知道n是多少
n就是n，它代表几项
其他回答 (2)
等于2的n加2次方-2的3次方
相关知识等待您来回答
学习帮助领域专家
当前分类官方群专业解答学科习题，随时随地的答疑辅导&&&&&& 给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。&
&&&&& 例如：N=2，1,2出现了1个“1”。
&&&&&&&& && N=12，1,2,3,4,5,6,7,8,9,10,11,12。出现了5个“1”。
问题求解：
&&&&&& 最直接的方法就是从1开始遍历到N，将其中每一个数中含有“1”的个数加起来，就得到了问题的解。
&&&& &代码如下：
1 publiclong CountOne3(long n)
3 long i =<span style="color:#,j =<span style="color:#;
4 long count =<span style="color:#;
5 for (i =<span style="color:#; i &= i&#43;&#43;)
8 while (j !=<span style="color:#)
<span style="color:# if (j %<span style="color:#==<span style="color:#)
<span style="color:#
count&#43;&#43;;
<span style="color:#
j = j /<span style="color:#;
<span style="color:#
<span style="color:#
<span style="color:# return
<span style="color:#
&&&&&&& 此方法简单，容易理解，但它的问题是效率，时间复杂度为O（N * lgN），N比较大的时候，需要耗费很长的时间。
&&&&&&&& 我们重新分析下这个问题，对于任意一个个位数n，只要n&=1,它就包含一个“1”；n&1，即n=0时，则包含的“1”的个数为0。于是我们考虑用分治的思想将任意一个n位数不断缩小规模分解成许多个个位数，这样求解就很方便。
&&&&&&& 但是，我们该如何降低规模？仔细分析，我们会发现，任意一个n位数中“1”的个位可以分解为两个n-1位数中“1”的个数的和加上一个与最高位数相关的常数C。例如，f(12) = f(10 - 1) &#43; f(12 - 10) &#43; 3,其中3是表示最高位为1的数字个数，这里就是10,11,12；f(132)=f(100 -1) &#43; f(132 - 100) &#43; 33，33代表最高位为1的数字的个数，这里就是100~132；f(232) = 2*f(100 - 1) &#43; f(32) &#43; 100，因为232大于199，所以它包括了所有最高位为1的数字即100~199，共100个。
&&&&&&& 综上，我们分析得出，最后加的常数C只跟最高位n1是否为1有关，当最高位为1时，常数C为原数字N去掉最高位后剩下的数字&#43;1，当最高位为1时，常数C为10bit，其中bit为N的位数-1，如N=12时，bit=1，N=232时，bit=2。
&&&&&& 于是，我们可以列出递归方程如下：
&&&&&& if(n1 == 1)
&&&&&&&&&& f(n) = f(10bit-1) &#43; f(n - 10bit)& &#43; n - 10bit&#43; 1;
&&&&&& else
&&&&&&&&&& f(n) = n1*f(10bit-1) &#43; f(n – n1*10bit) &#43; 10bit;
&&&&&& 递归的出口条件为：
&&&&&& if(1&n&10)& return 1;
&&&&& &else if (n == 0) return 0;
&&&&&& 基于此，编写如下代码：
1 publiclong CountOne(long n)
3 long count =<span style="color:#;
4 if (n ==<span style="color:#)
count =<span style="color:#;
6 elseif (n &<span style="color:#&& n &<span style="color:#)
count =<span style="color:#;
<span style="color:# long highest =//表示最高位的数字
<span style="color:# &int bit =<span style="color:#;
<span style="color:# while (highest &=<span style="color:#)
<span style="color:#
<span style="color:#
highest = highest /<span style="color:#;
<span style="color:#
bit&#43;&#43;;
<span style="color:#
<span style="color:#
<span style="color:# int weight = (int)Math.Pow(<span style="color:#, bit);//代表最高位的权重，即最高位一个1代表的大小
<span style="color:# &if (highest ==<span style="color:#)
<span style="color:#
<span style="color:#
count = CountOne(weight -<span style="color:#)
<span style="color:# &#43; CountOne(n - weight)
<span style="color:# &#43; n - weight &#43;<span style="color:#;
<span style="color:#
<span style="color:# else
<span style="color:#
<span style="color:#
count = highest * CountOne(weight -<span style="color:#)
<span style="color:# &#43; CountOne(n - highest * weight)
<span style="color:# &#43;
<span style="color:#
<span style="color:#
<span style="color:# return
<span style="color:#
&&&&&&& &此算法的优点是不用遍历1~N就可以得到f(N)。经过我测试，此算法的运算速度比解法一快了许多许多，数字在1010内时，算法都可以在毫秒级内结束，而解法一在计算109时，时间超过了5分钟。但此算法有一个显著的缺点就是当数字超过1010时会导致堆栈溢出，无法计算。
&&&&&&& 还有就是，我尝试了许久也没有计算出此算法的时间复杂度到底是多少，&#20284;乎是O（lg2N），我并不确定，希望知道的高手能给予解答。
&&&&&&& &解法二告诉我们1~ N中“1”的个数跟最高位有关，那我们换个角度思考，给定一个N，我们分析1~N中的数在每一位上出现1的次数的和，看看每一位上“1”出现的个数的和由什么决定。
&&&&&& <span style="color:#位数的情况：
&&&&&& 在解法二中已经分析过，大于等于1的时候，有1个，小于1就没有。
&&&&&& <span style="color:#位数的情况：
&&&&&& N=13,个位数出现的1的次数为2，分别为1和11，十位数出现1的次数为4，分别为10,11,12,13，所以f(N) = 2&#43;4。
&&&&&& N=23,个位数出现的1的次数为3，分别为1，11，21，十位数出现1的次数为10，分别为10~19，f(N)=3&#43;10。
&&&&&& 由此我们发现，个位数出现1的次数不仅和个位数有关，和十位数也有关，如果个位数大于等于1，则个位数出现1的次数为十位数的数字加1；如果个位数为0，个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关，也和个位数相关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，假如十位数大于1，则十位数上出现1的次数为10。
&&&&&& <span style="color:#位数的情况:
&&&&&& N=123
&&&&&& 个位出现1的个数为13:1,11,21，…，91,101,111,121
&&&&&& 十位出现1的个数为20:10~19,110~119
&&&&&& 百位出现1的个数为24:100~123
&&&&&& 我们可以继续分析4位数，5位数，推导出下面一般情况：&
&&&&&& 假设N，我们要计算百位上出现1的次数，将由三部分决定：百位上的数字，百位以上的数字，百位一下的数字。
&&&&&& 如果百位上的数字为0，则百位上出现1的次数仅由更高位决定，比如12013，百位出现1的情况为100~199,00~2199，…，，共1200个。等于更高位数字乘以当前位数，即12 * 100。
&&&&&& 如果百位上的数字大于1，则百位上出现1的次数仅由更高位决定，比如12213，百位出现1的情况为100~199,00~2199，…，，共1300个。等于更高位数字加1乘以当前位数，即（12 &#43; 1）*100。
&&&&&&& 如果百位上的数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。例如12113，受高位影响出现1的情况：100~199,00~2199，…，，共1200个，但它还受低位影响，出现1的情况是，共114个，等于低位数字113&#43;1。
&&&&&& 综合以上分析，写出如下代码：
1 publiclong CountOne2(long n)
3 long count =<span style="color:#;
4 long i =<span style="color:#;
5 long current =<span style="color:#,after =<span style="color:#,before =<span style="color:#;
6 while((n / i) !=<span style="color:#)
current = (n / i) %<span style="color:#;
before = n / (i *<span style="color:#);
<span style="color:#
after = n - (n / i) *
<span style="color:#
<span style="color:# if (current &<span style="color:#)
<span style="color:#
count = count &#43; (before &#43;<span style="color:#) *
<span style="color:# elseif (current ==<span style="color:#)
<span style="color:#
count = count &#43; before *
<span style="color:# elseif(current ==<span style="color:#)
<span style="color:#
count = count &#43; before * i &#43; after &#43;<span style="color:#;
<span style="color:#
<span style="color:#
i = i *<span style="color:#;
<span style="color:#
<span style="color:# return
<span style="color:#
<span style="color:#
&&&& 此算法的时间复杂度仅为O(lgN)，且没有递归保存现场的消耗和堆栈溢出的问题。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：90372次
积分：1841
积分：1841
排名：第9873名
原创：88篇
转载：50篇
评论：29条
(2)(1)(3)(1)(2)(7)(6)(7)(3)(11)(18)(8)(1)(4)(6)(24)(27)(7)