一道juniper的面试题，算法求改进，求时间复杂度~
题目来源自http://bbs.csdn.net/topics/390315847 #32楼
题目要求：
定义一个数字有以下的特征, 它可以被分成几个部分,而前面的部分相加起来的和是后面的部分.举例来说
1235813, 1+2=3; 2+3=5;3+5=8; 5+8=13;
112112224, 112+112=224;
1981100, 19+81=100;
122436, 12+24=36;
1299111210, 12+99=111,99+111=210;
要求写出一个函数,输入一个数字,判断这个数字是不是要求的这个数。
说者无意听者有心啊
http://blog.csdn.net/wlcw16/article/details/8303104
我自己写了个算法，但是感觉应该还会有简化的空间。
并且求大神帮忙算下时间复杂度，如果数的位数为n的话。
[解决办法]
你这算法根本就是错的。10111，可以分成10+1=11，你输出false。
[解决办法]
这样看一个数：d1 s1 d2 s2 d3 s3 ... dn sn，其中di是数字，si是可能分割的位置。
取定a1,a2后，要验证a1,a2开头的序列是否满足条件最坏的情况需要lgn次加法，以及n次位数比较。但我想平均下来应该为O(1),因为几乎所有的情况都会在第一次加法时就可以淘汰了。
a1,a2的取法有n(n-1)/2种，因为要从si中取两个。
所以时间复杂度为O(n^3)（或O(n^2)).
In [106]: def isLegal(n, i, j):
...: """取前i位为a1,第i+1到j位为a2,检测n是否由a1和a2生成的序列组成。"""
...: nextDigit = j
...: a1 = int(n[:i])
...: a2 = int(n[i:j])
...: while nextDigit<len(n): # n还有数字可用
...: a2, a1 = a1+a2, a2
...: s2 = str(a2)
...: if n.startswith(s2, nextDigit): #从n的第nextDigit位开始，与s2比较
...: nextDigit += len(s2)
...: else:
...: return False
...: return True
In [107]: def test(n):
...: for i in range(1, len(n)-1):
...: for j in range(i+1, len(n)-1):
...: if isLegal(n, i, j):
...: return True
...: return False
In [108]: test('1235814')
Out[108]: False
In [109]: test('1235813')
Out[109]: True
In [110]: test('112112224')
Out[110]: True
In [111]: test('1299111210')
Out[111]: True
[解决办法]
