分治法举例之x的n次方

• 分治法举例之x的n次方
• 问题
• 1.pow函数
• 2.简单实现
  • 递归
  • 循环
• 3.分治法实现
• 实验数据
• 结论

问题

(求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次方。

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

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

结论

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