预备知识

传值过程

1. 传递实参的副本
    

   int Abc(int a,int b,int c){return a+b+b*c+(a+b-c)/(a+b)+4;
   }
   void main(){int i=Abc(1,2,3); //调用int的拷贝构造函数将实参值拷贝给形参，即借用了实参的副本cout<<i<<endl;   //所以不会改变实参的值
   }

2. 若实参所占的内存很大，可以传递实参的地址，即指针
3. 拷贝构造函数

• 当用已存在的对象来创建一个新对象，对象作为传值参数，对象作为返回值时，触发拷贝构造函数
• 隐式的拷贝构造函数仅提供浅拷贝，显式的拷贝构造函数可提供参拷贝
• 当类包含指针成员时一般应自定义复制构造函数
  如果不声明拷贝构造函数，person p2=p1时会调用隐式的拷贝构造函数，把p1的地址直接给到p2。等到析构的时候，先析构p2，其实已经把p1的地址释放了，再析构p1的时候，重复释放内存，就会报错。

  class person{char *pName;
  public:person(char *pN){ //构造函数pName=new char[strlen(pN)+1]; //+1储存\0strcpy(pName,pN);}person(person &p){ //拷贝构造函数pName=new char[strlen(p.pName)+1];strcpy(pName,p.pName);}~person(){ //析构函数delete pName;}
  }
  void print(person p){cout<<p.pName<<endl;
  }
  void main(){person p1("zhang");person p2=p1; //调用person的拷贝构造函数print(p1);
  }

递归函数

1. 直接递归
   函数的代码中直接包含了调用它本身的语句
2. 间接递归
   在多个函数之间形成调用回路

   //累加数组元素
   template<class T>
   T rSum(T a[],int n){if(n>0)return rSum(a,n-1)+a[n-1];return 0;
   }

测试与调试

1. 黑盒法：未知具体代码，仅测试结果是否符合预期
2. 白盒法：已知具体代码
   （1）语句覆盖：使程序的每一条语句都至少执行一次
   （2）分支覆盖：使程序的每一个条件都取到true和false值
   （3）从句覆盖：每个条件的每个从句既能出现true也能出现false的情况
   （4）执行路径覆盖：使每条执行路径都得以执行
3. 注意测试边界值

程序性能分析

空间复杂度

1. 固定部分
   （1）指令空间：程序需要的存储空间
   （2）简单变量空间
   （3）常量空间
2. 可变部分
   （1）动态分配空间
   （2）递归栈空间：局部变量、形参所需的空间➡️递归深度（嵌套递归调用的最大层次）

//累加数组元素template<class T>
T sum(T a[],int n){T theSum=0;for(int i=0,i<n;i++)theSum+=a[I];return theSum;
} //所需的空间与n的值无关，S(n)=0template<class T>
T rSum(T a[],int n){if(n>0)return rSum(a,n-1)+a[n-1];return 0;
} //最大递归深度为n+1，S(n)=12(n+1)

时间复杂度

操作计数分析

程序运行中起主要作用且时间花费最多的操作

//多项式计算//鲁莽算法
template<class T>
T polyEval(T coeff[],int n,const T& x){T y=1, value=coeff[0];for(int i=1;i<=n;i++){y*=x;value+=y*coeff[I];}return value;
} //每次执行1次加法，2次乘法，一共n次//优化
template<class T>
T Horner(T coeff[],int n,const T& x){T value=coeff[n];for(int I=1;i<=n;i++)value=value*x+coeff[n-i];return value;
}//每次执行1次加法，1次乘法，一共n次

四种排序算法及其操作分析

1. 计数排序
   （1）先求元素在序列中的名次：对于每一个元素，将它与其左边的所有元素比较，谁大谁的名次就加1
   （2）将元素调整到与其名次对应的位置上

   template<class T>
   void rank(T a[],int n,int r[]){for(int i=0;i<n;i++)r[i]=0; //初始名次都为0for(int i=1;i<n;i++)for(int j=0;j<i;j++)if(a[j]<=a[i]) //每个数都和它左边的所有数做比较r[i]++; //谁大谁名次+1elser[j]++;
   }
   template<class T>
   void rearrange(T a[],int n,int r[]){T* u=new T[n+1]; //生成一个新的数组 ⚠️占用了额外空间for(int i=0;i<n;i++)u[r[i]]=a[I]; //把数按照名次排好 for(i=0;i<n;i++)a[i]=u[I]; //把排好序的数放入原来的数组delete []u; //释放内存
   }//update
   //原址排序
   template<class T>
   void rearrange(T a[],int n,int r[]){for(int i=0;i<n;i++)while(r[i]!=i){ //如果数字不是在它应该的位置上int t=r[i];swap(a[i],a[t]); //将数字和应该在的位置上的数字互换swap(r[i],r[t]); //记得把计数也呼唤}
   }

2. 选择排序
   （1）先找出最小的元素，把它移动到队首
   （2）在剩下的数中重复进行上述操作

   template<class T>
   void selectionSort(T a[],int n){for(int size=n;size>1;size--){ //size:还没有排序的个数int j=indexOfMax(a,size); //寻找最大元素的位置swap(a[j],a[size-1]); //把最大元素换到还没有排序的最后一个位置}
   } //比较次数：n(n-1)/2//update
   //比较次数：最好n-1 最坏n(n-1)/2
   template<class T>
   void selectionSort(T a[],int n){bool sorted=false; //判断是否有序的布尔值for(int size=n;!sorted&&(size>1);size--){ //无序才进入循环int indexOfMax=0;sorted=true; //假设有序for(int I=1;i<size;i++)if(a[indexOfMax]<=a[i])indexOfMax=i; //一直在这个语句内说明有序elsesorted=false; //无序swap(a[indexOfMax],a[size-1]);}
   }

3. ​​​​​冒泡排序

   template<class T>
   void bubble(T a[],int n){for(int i=0;i<n-1;i++)if(a[i]>a[i+1])swap(a[i],a[i+1]); //把大的元素移到右边
   }template<class T>
   void bubbleSort(T a[],int n){for(int i=n;i>1;i--)bubble(a,i);
   } //比较次数：n(n-1)/2//update
   template<class T>
   bool bubble(T a[],int n){bool swapped=false;for(int i=0;i<n-1;i++)if(a[i]>a[i+1]){swap(a[i],a[i+1]); //把大的元素移到右边swapped=true; //交换了，说明无序}return swapped; //如果一直没有交换，即为有序
   }template<class T>
   void bubbleSort(T a[],int n){for(int i=n;i>1&&bubble(a,i);i--) //只有当有交换，即无序时，才继续调用冒泡排序
   }

4. 插入排序
   利用了原排列的有序性

   template<class T>
   void insertionSort(T a[],int n){for(int i=1;i<n;i++){T t=a[i]; //要插入的数int j;for(int j=i-1;j>=0&&t<a[j];j--) //从后往前找比要插入的数大的数，找到了才进入循环a[j+1]=a[j]; //把比目标数大的数往后移一格//跳出循环的时候，j在要插入的位置的前一个a[j+1]=t; //插入数字}
   }
   //比较次数：最好n-1 最坏n(n-1)/2//update
   //将元素放到有序数列的中间，利用二分查找比较

渐进记法

大O记法

1. 大O记法：表示函数的上界
2. 松散界限：不是最小上限
3. 错误界限

记法

表示函数的下限

记法

函数的上下限都是同一个函数

 小O记法

严格的上限