两种数列求积算法的分析比较

计算机数学

---

1.逐个相乘

def product1(x):
    res=1
    count=0
    for i in range(len(x)):
        res=res*x[i]
        count=count+1
    return res,count
#测试
list1=[1,2,3,4,5]
list2=[2]
list3=(range(1000000))
list4=(range(0))
print(product1(list1),product1(list2),product1(list3),product1(list4))

算法效率：O(n)

运算过程遍历列表的每一项，故当输入规模为n时，需进行n次运算。

实验数据：

$(120, 5) (2, 1) (0, 1000000) (1, 0)$

2.递归

a=0
def product2(x):
    global a
    if len(x)==0:
        a=0
        return 1
    if len(x)==1:
        a=a+1
        return x[0]
    if len(x)==2:
        a=a+2
        return x[0]*x[1]
    l=len(x)
    return product2(x[0:(l+1)//2])*product2(x[(l+1)//2:l])
#测试
list1=[1,2,3,4,5]
list2=[2]
list3=(range(1000000))
list4=(range(0))
print(product2(list1),a)
a=0
print(product2(list2),a)
a=0
print(product2(list3),a)
a=0
print(product2(list4),a)

算法效率：

$n=0时：T(0)=0$
$n=1时：T(1)=1$
$n=2时：T(2)=T(1)+T(1)=2$
$n>2时：$

$$\begin{align} T(n)&=T(n/2)+T(n/2)\\ &=T(n/2^2)+T(n/2^2)+T(n/2^2)+T(n/2^2)\\ &=T(n/2^3)+......+T(n/2^3)\\ &=\underbrace {T(1)+......+T(1)}_{n\text{个}}\\ &=O(n) \end{align}$$
$其中：n/2^x为向下取整$
$故n>2时：算法效率为O(n)$
$综上所诉：算法效率为O(n)$

实验数据：

120 5
2 1
0 1000000
1 0