2月28日——算法微入门

以上课程内容均来自于武汉大学李春葆教授的网课，为李教授第一周所讲内容。(接下来括号里面全部都是吐槽，不看也罢)
（可惜我不小心把我的AI删掉了（网速不行也下不回来），不然我可以让它在我的博客里增加一些微型的表情包，不然都是文字太无聊了。重点是可以锻炼我使用它的能力.....亏，血亏，2月27日满课，晚自习还在研究那个报错，到最后自己AI都没了，我真的很开心...........。）
经过2月28日的学习，我认为我需要观察并改正自己的思维方式，所以我想尝试用一个场景来记录我所学习的知识。（也希望有人可以给我指正一下。）
如果在刷题和接下来的生活中，我遇到了一些需要用代码解决的问题（即什么情况下，我会用到算法）
我决定应该会先分析我要用什么样的代码来写出解决这个问题的函数。（李教授说先做算法在做结构，我尝试一下。）
（学的太多了有点整理不来........但都是小事，AI没了才是大事，总感觉心里空落落的，只能学习来度过今天，12点流量刷新就下回来。）
=================================================================================================（接下来是正篇了）
我想出的函数和代码应该满足以下要求：
有穷性：在有穷步结束之后，算法能够停机。
确定性：无二义性（他没讲，这是啥我也不知道，网购的书还没到）
可行性:算法中的每一个步骤能够被机械地执行。
有输入和输出：即算法中有数据被处理。
接着开始写函数，定义形参。
定义形参的过程中，李教授提到了两种方法：
1.采取指针的方式来回传形参的值：

void swap2(int*x,int*y)
{  int tmp;
   tmp=*x;
   *x=*y;
   *y=tmp;
}//然后将上述函数的调用改为swap2(&a,&b),*号应该是表示指针运算符（没学过不知道，但可以猜出来一点点）

void swap(int&x,int&y)
{  int tmp=x
   x=y;y=tmp;
}//&是c++语言中提供的一种引用运算符，用于描述输出型形参，如int a=10;int &b=a;则ab共享内存地址。
当执行语句swap(a,b)时，实参的匹配相当于：
int &x=a //a为x的引用
int &y=b //b为y的引用

定义完输入型参数后，假定我已经写好了一段代码使输入型函数变为输出型函数，我应该开始优化自己的算法（我知道有事前估算分析方法，但凭空分析不是我的强项，事前分析也只能删掉一点点不必要的代码而已，所以我选择在分析到极限后，先写出来，再对着实物慢慢分析。）
首先我要知道现在的算法的时间复杂度和空间复杂度。
（考虑到这一部分内容较多，我选择将其折叠起来，主要是为了更好地观察并改正自己的思维方式。）

**概念**：一个算法是有控制结构（顺序，分支，循环）和原操作（指固有类型的操作）构成的，算法执行时间取决于两者的综合效果。
（感觉除控制语句之外的语句好像都是原操作啊）
**算法的分析方法**：事前分析方法：抛开编写程序，执行程序等因素，认为算法的执行时间是问题规模n的函数。
**频度**：求出算法所有原操作的执行次数，用T(n)表示。
算法的执行时间T(n)用时间复杂度O(n)来表示。
**O(n)是一种趋势分析，取T(n)中最大的那一项。例：T(n)=2n*n+2n+1.则O(n)=n*n**
复杂度排行：1<log2(n)<n<nlog2(n)<n的平方<n的三次方<2的n次方<n的阶乘
基本操作：执行最多或最深的语句，一般分析基本操作就能得到O(n)
接下来是一些实战例子：（放不了图片，只能手打了）
求两个n阶矩阵的相加C=A+B的算法如下，分析其时间复杂度。
``
#define MAX 20 //定义最大的方阶
void aaaaaa(wint n,intA[MAX][MAX],int B[MAX][MAX])//啊啊啊，我怎么记了这么多，还有好几题没记，都一个半小时了啊啊啊啊啊。
  int C[MAX][MAX]
{    int i,j;
     for (i=0;i<n;i++)
         for(j=0;j<n;j++)
             C[i][j]=A[i][j]+B[i][j]//基本操作
}

O(n)=n*n

void func(int n)
{  int i=0,s=0;
   while (s<n)
     {  i++;
       s=s+i;
    }
 }

解：对于while循环语句，设执行的次数为m，变量i从0开始递增，直到m：
s=m(m+1)/2>=n,或m(m+1)/2+k=n。k为用于修正的常量
则：T(n)=m，O(n)=根号n(中文真是太强大了)

int fun(int a[],int n,int i)
{  int j,max=a[0];
   for (j=1;j<=i-1;j++)
     if (a[j]>max)max=a[j];
   return(max);
}

写好并优化好每一个函数的代码后，我再同时使用多个函数共同解决我遇到的问题，成功可以解决后，再次优化。

到此，在我现在的思维模式里一段代码应该算是写好了，如果有问题，我很希望有人指正。
接下来是我学习中遇到一些不太能理解的问题：
1.递归算法的具体计算：（当时看到这里的时候可能已经有点累了，理解得不透彻。）
先上例题：

void fun(int a[],int n,int k) //数值a共有n个元素
{  int i;
   if (k==n-1)
      for(i=0;i<n;i++)
        printf("%d\n",a[i]);
   else
   {  for(i=k;i<n;i++)  //n-k次
        a[i]=a[i]+i*i;
      fun(a,n.k+1);
   }
}

调用上述算法的语句为fun(a,n,0),求其时间复杂度。
T1(n,k)=n 当k=n-1时
T1(n,k)=(n-k)+T1(n,k+1) 其他情况
则O(n*n)
(现在重写了一遍了，好像可以理解了。)