python-2.7 - 我的 Python 程序的复杂性是多少？复杂性新手

Question

def multiplyItself():
 i=[2,3,1,4]
 j=[]
 length=len(i) # 0 1 2 3
 print 'input string',i
 for l in range(length):
  if l==0:
    j.append(mul(i[l+1::]))
  if l>0:
    print i[l+1::]
    print i[0:l]
    j.append(mul(i[l+1::])*mul(i[0:l]))
 print j


def mul(l):
 sum=1
 for i in l:
   sum=sum*i
 return sum

def main():
 print 'test multply'
 multiplyItself()


main()

---

上面的 python 代码有效，但我不确定程序的复杂性。谁能给我更多的见解？

实际问题如下：输入 [2,3,1,4] 输出 [12,8,24,6]

将所有字段相乘，除了它自己的位置。

限制： 1. 不使用除法 2. O(n) 中的复杂性

Answer 1

让我们一步一步来：

1. mul(l)对 的每个元素执行操作l。因此，它的复杂性是O(len(l))。
2. 由于j.append(mul(i[l+1::])*mul(i[0:l]))对O(len(i))元素进行操作，因此其复杂度为O(len(i)).
3. 由于j.append()是重复len(i)次数，因此总体复杂度是O(len(i)*len(i))或O(n**2)（其中n是len(i)）。

总之，您需要一个不同的算法。

提示（鼠标悬停显示）：

如果将所有元素相乘会有所帮助吗？