14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！

程序的复杂性

• 时间的复杂度
• 空间的复杂度

这是我在力扣网上找的一个题，题目中有这样的限制条件，你知道什么是时间的复杂的吗？你知道该怎样计算时间的复杂度吗?

时间的复杂性

好的算法的判断方法是：高效率、低存储。那么计算运行的速度，学习时间的复杂性是十分有必要的。

算法的时间复杂度就是算法运行所需的时间。由于相同配置的计算机进行一次基本运算的时间是一定的，可以用算法基本运算的执行次数来衡量算法的效率，因此我们将算法基本运算的执行次数作为时间复杂度的衡量标准。

  观察算法1-1并分析算法的时间复杂度
  
  //算法1-1
  int sum = 0;//运行1次
  int total = 0;//运行1次
  for (int i = 1; i <= n; i++)//运行n+1次
  {
	sum = sum + i;//运行n次
	for (int j = 1; j <= n; j++)//运行n*(n+1)次
	{
		total = total + i * j;//运行n*n次
	}
  }

把算法1-1中所有语句运行的次数加起来：1+1+n+1+n+n*(n+1)+n*n。这可以用一个函数T(n)来表示：

      T(n)=2n^2+3n+3

当n足够大时，例如n=10^5，T(n)=2*10^10+3*10^5+3。可以看出，算法的运行时间主要取决于最高项。其实时间的复杂度也与最高项息息相关，接下来让我们化简求时间的复杂度。
化简得规则为：

• 忽略常数项 //T(n)=2n^2+3n
• 忽略低阶项 //T(n)=2n^2
• 忽略最高阶的系数 //T(n)=n^2

所以f(n)=n^2，时间复杂度的表示为 O(f(n))，
所以则时间复杂度的表示为 O(n^2)

以上就是时间复杂度的求法，让我们来几道题练练手吧：

• 第一题

  //算法1-2
  int i = 1;        //运行1次
  while (i <= n)    //假设运行x次
  {
      i = i * 2;    //假设运行x次
  }
  
  对于算法1-2我们无法立即确定while以及i=i*2语句运行了多少次。这时可假设运行了x次，
  每次运行后  i的值为2、2^2、...、2^x，当2^x>n结束，此时x>log_2^n，所以while运行的次数为
  log_2^n+1， i=i\*2运行次数为log_2^n，所以算法1-2的运行次数为1+2log_2^n，时间的复杂度
  为O(f(n))=O(log_2^n)。
  

在计算时间复杂度时，可以只考虑对算法运行时间贡献大的语句，而忽略那些运行次数少的语句。循环语句中处在循环内层的语句往往运行次数最多，它们时对运行时间贡献最大的语句。例如，在1-1中，total=total+i*j是对算法贡献最大的语句，只计算该语句的运行次数即可。

不是所有的算法都能直接计算运行次数
例如算法1-3，在数组a[n]中顺序查找x并返回其下标i。如果没有找到，则返回-1。

 //算法1-3
int  findx(int x)
{
        int i = 0;
        for(i = 0; i<n; i++)
        if(a[i] == x)
              return 1;
        return 0;
}

对于该算法，很难计算到底执行了多少次，因为运算次数依赖于数组中x的位置。如果第一个元素是x，则执行一次（最好的情况）；如果最后一个是x，则执行x次（最坏的情况）；如果分布概率均等，则平均运行次数为(n+1)/2。
//
有些算法，如排序、查找、插入算法等，可以分为最好、最坏和平均情况分别求算法渐进复杂度。但考察一个算法时通常考查最坏的情况，而不是考察最好的情况，最坏的情况对衡量算法的好坏具有实际意义。

空间的复杂度

空间的复杂度：算法占用空间的大小。
算法复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：

• 输入/输出数据

• 算法本身

• 额外需要的辅助空间

  输入/输出数据占用的空间时必需的，算法本身占用的空间可以通过精简算法来缩减，但缩减的量是很小的，可以忽略不计。算法在运行时所使用的辅助变量占用的空间（即辅助空间）才是衡量算法空间复杂度的关键因素。
  

我们可以类比时间复杂度，当n趋近于无限大时，常量和低阶项都可以忽略不记。在这里，输入/输出、算法本身可以忽略不记。

请分析算法1-4的空间复杂度

void swap(int* x, int* y)      //交换x，y的值
{
       int temp;
       temp = *x;         //temp为辅助空间
       *x = *y;
       *y = temp;
}

算法1-4使用了辅助空间temp，空间复杂度为O(1)

请分析算法1-5（递归）空间复杂度

int fac(int n){ //计算n的阶乘
      if(n == 0&&n == 1)
           return 1;
      else
           return n*fac(n-1);
}

阶乘是典型的递归调用问题，递归包括递推和回归。递推是将原问题不断分解成子问题，直至满足结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。

请计算n=5的空间复杂度。

计算机使用一种称为“栈”的数据结构，“栈”类似于一个放盘子的容器，每次从顶端放进去一个，拿出来的时候只能从顶端拿一个，不允许从中间插入或抽取，因此，称为“先进后出”。

           5的阶乘进栈的过程

        5的阶乘出栈的过程

则5的阶乘的辅助空间是5，空间复杂度为5
则n的阶乘的空间复杂度为n