def triangles(A):
n = len(A)
result = 0
for x in xrange(n):
z=x+2
for y in xrange(x + 1, n):
while (z < n and A[x] + A[y] > A[z]):
z += 1
result += z - y - 1
return result
这是Codility解决方案的一个示例（https://codility.com/media/train/13-CaterpillarMethod.pdf）
他们在手册中声称此算法的大Oh为O（N ^ 2）
但是我认为big-Oh是O（N ^ 3），因为最坏的情况是
（n-1）（n-2）+（n-2）（n-3）+ ..... + 1 * 0
所以我认为它的大哦是O（N ^ 3）。
谁能解释为什么该算法的big-Oh是O（N ^ 2）？
还是我说的对吗？
该while遍历z意志，accumulately，只运行一次（<n次）为每次执行for循环以上y，由于z是仅重置在范围外的的for遍历y。因此，“内部范围”的粗略上限循环计数沿线n*(n+n)（位于中O(n^2)）而不是n*n*n。在计算复杂度时，我们不妨将while循环z视为与循环平行的for循环y，而不是嵌套在for循环中的一个循环y。
即，与例如相同的复杂度：
def triangles(A):
n = len(A)
result = 0
for x in xrange(n):
z=x+2
while (z < n)
z += 1
for y in xrange(x + 1, n):
...
return result
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句