61-算法解析及优化拓展

4.10.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：算法中有3层嵌套的for循环，其时间复杂度为O(n³)。

（2）空间复杂度：使用了3个二维数组求解c[i][j]、w[i][j]、s[i][j]，所以空间复杂度为O(n²)。

2．算法优化拓展

如果按照普通的区间动态规划进行求解，时间复杂度是O(n³)，但可以用四边形不等式优化。

s[i][j]表示取得最优解c[i][j]的最优策略位置。

k的取值范围缩小了很多，原来是区间[i，j]，现在变为区间[s[i][j−1]，s[i+1][j]]。经过优化，算法时间复杂度可以减少至O(n²)，时间复杂度的计算可参看4.8.6节。

优化后算法：

//program 4-8-1
#include<iostream>
#include<cmath>           //求绝对值函数需要引入该头文件
using namespace std;
const int M=1000+5;
double c[M][M],w[M][M],p[M],q[M];
int s[M][M];
int n,i,j,k;
void Optimal_BST()
{
     for(i=1;i<=n+1;i++)
     {
          c[i][i-1]=0.0;
          w[i][i-1]=q[i-1];
     }
     for(int t=1;t<=n;t++)//t为关键字的规模
          //从下标为i开始的关键字到下标为j的关键字
          for(i=1;i<=n-t+1;i++)
          {
               j=i+t-1;
               w[i][j]=w[i][j-1]+p[j]+q[j];
               int i1=s[i][j-1]>i?s[i][j-1]:i;
               int j1=s[i+1][j]<j?s[i+1][j]:j;
               c[i][j]=c[i][i1-1]+c[i1+1][j];//初始化
               s[i][j]=i1;//初始化
               //选取i1+1到j1之间的某个下标的关键字作为从i到j的根，如果组成的树的期望值当前最小，则k为从i到j的根节点
               for(k=i1+1;k<=j1;k++)
               {
                    double temp=c[i][k-1]+c[k+1][j];
                    if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)//C++中浮点数因为精度问题不可以直接比较
                    {
                         c[i][j]=temp;
                         s[i][j]=k;//k即为从下标i到j的根节点
                    }
               }
               c[i][j]+=w[i][j];
          }
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
     if(flag==0)
     {
          cout<<"S"<<s[i][j]<<" 是根"<<endl;
          flag=1;
     }
     int k=s[i][j];
     //如果左子树是叶子
     if(k-1<i)
     {
          cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
     }
     //如果左子树不是叶子
     else
     {
          cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
          Construct_Optimal_BST(i,k-1,1);
     }
     //如果右子树是叶子
     if(k>=j)
     {
          cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
     }
     //如果右子树不是叶子
     else
     {
          cout<<"S"<<s[k+1][j]<<" is the right child of "<<"S"<<k<<endl;
          Construct_Optimal_BST(k+1,j,1);
     }
}
int main()
{
     cout << "请输入关键字的个数 n:";
     cin >> n;
     cout<<"请依次输入每个关键字的搜索概率:";
     for (i=1; i<=n; i++ )
           cin>>p[i];
     cout << "请依次输入每个虚结点的搜索概率:";
     for (i=0; i<=n; i++)
           cin>>q[i];
     Optimal_BST();
     // /*用于测试
     for(i=1; i<=n+1;i++)
     {
            for (j=1; j<i;j++)
              cout <<"\t" ;
            for(j=i-1;j<=n;j++)
              cout << w[i][j]<<"\t" ;
            cout << endl;
     }
      for(i=1; i<=n+1;i++)
     {
            for (j=1; j<i;j++)
              cout <<"\t" ;
            for(j=i-1; j<=n;j++)
              cout << c[i][j]<<"\t" ;
            cout << endl;
     }
     for(i=1; i<=n;i++)
     {
            for (j=1; j<i;j++)
              cout << "\t" ;
            for(j=i-1; j<=n;j++)
              cout << s[i][j]<<"\t" ;
            cout << endl;
     }
     cout << endl;
     // */用于测试
     cout<<"最小的搜索成本为："<<c[1][n]<<endl;
     cout<<"最优二叉搜索树为：";
     Construct_Optimal_BST(1,n,0);
     return 0;
}