MQL4求解6次二项式系数三类代码的Big O时间复杂度分析

以下三段代码用于求解幂次为6的二项式展开式初始系数。根据二项式定理，$(x + y)^6 = x^6 + 6x^5y + 15x^4y2 + 20x^3y3 + 15x^2y4 + 6xy^5 + y^6$，程序固定输入6时可输出系数序列1、6、15、20、15、6、1。以下分别给出三种实现方式的代码，以及输入固定为6时对应的Big O时间复杂度。

第一种方法：帕斯卡三角法 #

实现代码如下：

void OnInit()
  {
   int P0, P1, P2, P3, P4, P5, P6, P7, P8,P9, P10, P11, P12, P13, P14;
   int I1, I2, I3, I4, I5, I6, I7, I8,I9, I10, I11, I12, I13;
   for (int row = 0; row <= 6; row++)
     {
      for (int col = 1; col <= 13; col++)
        {
         if (row == 0)
           {
            I7 = 1;
           }
         else 
           {
            I1 = P0 + P2;
            I2 = P1 + P3;
            I3 = P2 + P4;
            I4 = P3 + P5;
            I5 = P4 + P6;
            I6 = P5 + P7;
            I7 = P6 + P8;
            I8 = P7 + P9;
            I9 = P8 + P10;
            I10 = P9 + P11;
            I11 = P10 + P12;
            I12 = P11 + P13;
            I13 = P12 + P14;
           } 
        }
      P1 = I1; P2 = I2; P3 = I3; P4 = I4; P5 = I5; P6 = I6; P7 = I7; P8 = I8; P9 = I9; P10 = I10; P11 = I11; P12 = I12; P13 = I13;
     }
   if(I1 != 0) Print(I1);
   if(I2 != 0) Print(I2);
   if(I3 != 0) Print(I3);
   if(I4 != 0) Print(I4);
   if(I5 != 0) Print(I5);
   if(I6 != 0) Print(I6);
   if(I7 != 0) Print(I7);
   if(I8 != 0) Print(I8);
   if(I9 != 0) Print(I9);
   if(I10 != 0) Print(I10);
   if(I11 != 0) Print(I11);
   if(I12 != 0) Print(I12);
   if(I13 != 0) Print(I13);
  }

时间复杂度分析 #

代码中两层循环的边界均为写死的固定常量：外层循环固定执行7次，内层循环固定执行13次，循环内的赋值运算、循环外的条件判断与打印操作的执行次数也全部为固定值，不存在随输入规模变化的可变执行逻辑，因此时间复杂度为 O(1)。

第二种方法：阶乘公式法 #

实现代码如下：

void OnInit()
  {
   int I1, I2, I3, I4, I5, I6, I7;
   I1 = (6 * 5 * 4 * 3 * 2 * 1) / ((1) * (6 * 5 * 4 * 3 * 2 * 1));
   I2 = (6 * 5 * 4 * 3 * 2 * 1) / ((1) * (5 * 4 * 3 * 2 * 1));
   I3 = (6 * 5 * 4 * 3 * 2 * 1) / ((2 * 1) * (4 * 3 * 2 * 1));
   I4 = (6 * 5 * 4 * 3 * 2 * 1) / ((3 * 2 * 1) * (3 * 2 * 1));
   I5 = (6 * 5 * 4 * 3 * 2 * 1) / ((4 * 3 * 2 * 1) * (2 * 1));
   I6 = (6 * 5 * 4 * 3 * 2 * 1) / ((5 * 4 * 3 * 2 * 1) * (1));
   I7 = (6 * 5 * 4 * 3 * 2 * 1) / ((6 * 5 * 4 * 3 * 2 * 1) * (1));
   Print(I1);
   Print(I2);
   Print(I3);
   Print(I4);
   Print(I5);
   Print(I6);
   Print(I7);
  }

时间复杂度分析 #

代码没有任何循环或递归逻辑，所有组合数计算全部是硬编码的常量乘除运算，7个系数的赋值、后续7次打印操作的总执行次数完全固定，和输入规模无关，因此时间复杂度为 O(1)。

第三种方法：表格递推法 #

实现代码如下：

void OnInit()
  {
   int I1, I2, I3, I4, I5, I6, I7;
   I1 = 1;
   I2 = (6 * I1) / 1;
   I3 = (5 * I2) / 2;
   I4 = (4 * I3) / 3;
   I5 = (3 * I4) / 4;
   I6 = (2 * I5) / 5;
   I7 = (1 * I6) / 6;
   Print(I1);
   Print(I2);
   Print(I3);
   Print(I4);
   Print(I5);
   Print(I6);
   Print(I7);
  }

时间复杂度分析 #

代码利用二项式系数的递推关系，从第一个初始系数开始逐次计算后续6个系数，总共仅执行7次赋值运算、7次打印操作，总执行步骤为固定常量，没有随输入规模增长的执行逻辑，因此时间复杂度为 O(1)。

内容的提问来源于stack exchange，提问作者Peter