Какова сложность моей программы на 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 работает, но я не уверен в сложности программ. Кто-нибудь может дать мне больше понимания?

Актуальный вопрос ниже: input [2,3,1,4] output [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)).

В заключение вам нужен другой алгоритм.

Подсказка (при наведении мыши):

Поможет ли вам умножить все элементы вместе?