欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Pow,求x的y次幂

程序员文章站 2022-07-12 12:03:27
...

算法分析:很显然用递归。但是直接用递归会造成栈溢出,时间复杂度是o(n)。所以要用分治思想,时间复杂度是o(logN)。

public class Power {
	//栈溢出,时间复杂度是o(n)
	public double myPow(double x, int n) 
	{
		if(n < 0)
		{
			return 1/myPow(x, -n);
		}
		else if(n == 0)
		{
			return 1;
		}
        else
        {
        	return x*myPow(x, n - 1);
        }
    }
	//分治思想,时间复杂度是o(logN)
	public double myPow2(double x, int n)
	{
		if(n < 0)
		{
			return 1/power(x, -n);
		}
		else
		{
			return power(x, n);
		}
	}
	public double power(double x, int n)
	{
		if(n == 0)
		{
			return 1;
		}
		
		double temp = power(x, n/2);
		if(n%2 == 0)
		{
			return temp*temp;
		}
		else
		{
			return x*temp*temp;
		}
	}
}