如何降低Python中计算数组元素三重乘积和的三重循环O(n³)时间复杂度？

Hey there! Let's fix that inefficient triple loop. Your original code calculates the sum of all possible triple products (including repeated elements/indices) by iterating through every combination of three elements in the array—this works, but it's way too slow for large arrays because of its O(n³) time complexity.

The Mathematical Trick #

Here's the key insight: the sum of every possible triple product i*j*k for all i,j,k in the array is exactly equal to the cube of the array's total sum.

Let me break that down with algebra:

If S = a₁ + a₂ + ... + aₙ, then S³ = (a₁+a₂+...+aₙ) × (a₁+a₂+...+aₙ) × (a₁+a₂+...+aₙ)
When you expand this product using the distributive property, you end up adding every single possible triple product a_i*a_j*a_k—which is exactly what your triple loop is doing.

Optimized Code #

With this trick, we can rewrite the code in O(n) time (since calculating the sum of the array only requires a single pass):

def calculate_triple_product_sum(arrn):
    array_sum = sum(arrn)
    return array_sum ** 3

Quick Verification #

Let's test this with a small example to make sure it matches your original code:

• Take arrn = [1, 2]
• Original loop result: 1*1*1 + 1*1*2 + 1*2*1 + 1*2*2 + 2*1*1 + 2*1*2 + 2*2*1 + 2*2*2 = 27
• Optimized result: (1+2)³ = 3³ = 27

Perfect, they match!

Edge Case Note #

If you actually need the sum of triple products where indices are distinct (i.e., i≠j≠k or i<j<k), the formula changes slightly. But based on your original triple loop (which uses all possible combinations including repeats), the above solution is exactly what you need.

内容的提问来源于stack exchange，提问作者Chandrachud Pati