题目：

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);

}

 

 

 

免责声明：本文为网络用户发布，其观点仅代表作者个人观点，与本站无关，本站仅提供信息存储服务。文中陈述内容未经本站证实，其真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。