Pow,求x的y次幂
2024-09-04 14:57:33
算法分析：很显然用递归。但是直接用递归会造成栈溢出，时间复杂度是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;
}
}
}
最新文章
- ResponsibleChain(责任链模式)
- C++find函数
- bzoj 1821: [JSOI2010]Group 部落划分 Group
- POJ 3299 Humidex 难度:0
- UIBlurEffect实现模糊效果
- Genymotion 模拟器 VirtualBox
- Rationnal Rose2003安装并破解
- Angularjs循环二维数组
- PHP+ajaxForm异步带进度条上传文件实例
- Tomcat 报错的解决方法：The APR based Apache Tomcat Native library which allows optimal
- Android Studio 2.2 新功能详解
- UNIX网络编程——TCP/IP简介
- ROS_Kinetic_01 在ubuntu 16.04安装ROS Kinetic 2017.01更新
- 为什么我的会话状态在ASP.NET Core中不工作了？
- Linux下printf、fprintf、sprintf的区别
- Linux下一台服务器Redis主从复制（master-slave）配置
- SqlServer主键
- SIEVE 线性筛
- 学习Python 新去处：Python 官方中文文档
- day19常用模块2