两种数列求积算法的分析比较[作业]

对比以下两种数列求积算法，说明并验证它们的效率。
第一个算法逐个元素相乘；第二个算法使用递归，把元素分成两组分别进行相乘。除了理论分析，最好有实验数据。

# Input: Given a sequence of number X
# Output: The product of all the numbers in X
def product1(X):
    res = 1
    for i in range(len(X)):
        res *= X[i]
    return res

# Input: Given a sequence of number X
# Output: The product of all the numbers in X
 def product2(X):
       if len(X) == 0: return 1
       if len(X) == 1: return X[0]
       if len(X) == 2: return X[0]*X[1]
       l = len(X)
       return product2(X[0:(l+1)//2]) * product2(X[(l+1)//2: l])

解答

1. 这是一位大一新生的解答，除了军训他还没有经过大学学习。值得表扬。

2. 这是一位高二有NOIP经历的学生解答。这是一种耐人寻味的解答。

两种方法的渐进复杂度都是O(n) 。正常乘法的话直接for循环快。因为分治的话感觉常数会大一点。高精度乘法的话分治快，因为时间复杂度会更优秀一点。

3. 这是所谓高手的解答，而是据说是世界闻名的密码学大家。我给一个差评！！！

This is much faster than multiplying sequentially first times second times third etc., for essentially the same reason that merge sort is much faster than insertion sort.