题目：
1、计算  （分治法）
问题描述
对于给定的n，要求在O(n)步内计算出  ，同时分析该程序的时间复杂性和空间复杂性。
输入：要计算的n,
输出：
思想：
1． 用普通算法实现计算量为  数量级；
2． 用分治法实现算法为O(n)级的
分治法具体实现：
利用函数：
F(n)= 
程序
//*************************************************************************************
//对于给定的n，要求在O(n)步内计算出2的2的n次幂 ，同时分析该程序的时间复杂性和空间复杂性。
//利用分治法解题
//author:dongkaiying
//use the common method ,we can find that if we use 'double ',the 'n' can only be the
//region lower than 9; so we must find a better method to reduce the complexity of the
//method.We use the "fenzhifa" we called.
//*************************************************************************************
#include<iostream.h>
#include<stdio.h>
double common_M(int n);
double FenZhi_M(int n);
void main()
{
cout<<"Please enter the 'n' you need:"<<endl;
int n;
cin>>n;
//use the easiest method to compute the value;
double j=common_M(n);
cout<<"Use the common method to compute the value is:"<<j<<endl;
double m=FenZhi_M(n);
cout<<"Use another common method to compute the value is:"<<m<<endl;
return;
}
//this method's complexity .:2's n cimi
double common_M(int n)
{
double result=1;
double result_1=1;
for(int x=1;x<=n;x++)
{
result*=2;
}
for(x=1;x<=result;x++)
{
result_1*=2;
}
return result_1;
}
//use the digui method;
double FenZhi_M(int n)
{
if(n==1)
return 4;
else
return FenZhi_M(n-1)*FenZhi_M(n-1);
}
|
本类阅读TOP10