배열 요소의 모든 쌍의 제품 합계

Question

배열에 [10,20,30,40]이있는 경우. 10 * 20 + 10 * 30 + 10 * 40 + 20 * 30 + 20 * 40 + 30 * 40을 계산해야합니다. 곱셈과 덧셈을 모두 일정 시간이 걸린다 고 가정합니다. O (n)을 사용하여 평가할 수 있습니까?

Answer 1

확실히.

def sumproductsofpairs(lst): 
    total = 0 
    psum = 0 
    for x in lst: 
     total += psum * x 
     psum += x 
    return total