分治法举例之x的n次方

分治法举例之x的n次方

问题

(求x^n是很简单的事)

1.pow函数

python有pow函数。直接调用

pow(232, 1000)

结果>时间>python xn1.py 0.02s user 0.01s system 89% cpu 0.038 total

2.简单实现

递归

O(n)的时间复杂度

def xn(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        return x * xn(x, n-1)



print(xn(232, 1000))

时间>RuntimeError: maximum recursion depth exceeded
python xn.py 0.03s user 0.03s system 81% cpu 0.071 total

超了递归深度。。

循环

def xn(x, n):
    if n == 0:
        return 1
    else:
        ret = 1
        while n > 0:
            ret *= x
            n -= 1
        return ret




print(xn(232, 1000))

时间>python xn3.py 0.02s user 0.02s system 89% cpu 0.046 total

3.分治法实现

def xn(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        if n%2 == 0:
            return xn(x, int(n/2)) * xn(x, int(n/2))
        else:
            return xn(x, int(n/2)) * xn(x, n-int(n/2))



print(xn(232, 1000))

时间>
python xn2.py 0.02s user 0.01s system 83% cpu 0.046 total

实验数据

实验1数据: 232的1000次方。

方法 时间
pow 0.038
一般实现(递归) 0.071超递归栈,无结果
一般实现(循环) 0.046
分治法 0.046

实验2数据: 232的10000次方。

方法 时间
pow 0.056
一般实现(循环) 0.080
分治法 0.070

实验2数据: 232的100000次方。

方法 时间
pow 1.195
一般实现(循环) 3.469
分治法 1.411

结论

  1. 递归实现需要注意到递归栈深度问题。
  2. 能用库函数就尽量用库函数。库函数一般是C实现,实现的比较高效。 没有库函数时,数据量小可以用最简单的方式实现,但数据量大时,一定得想有什么算法适合解决该问题。

发表评论

电子邮件地址不会被公开。 必填项已用*标注