活动地址：CSDN21天学习挑战赛

什么是算法？

从事程序编写的朋友都知道算法是非常重要的，算法简单来说就是解决问题的方法，一个问题可以有很多种解决办法，也就是多种算法。一个算法的好坏决定了要消耗多少计算机资源，是否能被更多的人使用和接受，所以在如今的面试中，越来越重视对算法的考察

评定算法优略的指标

程序运行时就是cpu与内存的交互，因此算法好坏的优略指标与cpu处理时消耗的算力及占用的内存空间息息相关，故通过时间复杂度和空间复杂度来评定

时间复杂度

算法的时间复杂度并不是说电脑通过该算法解决问题所消耗的时间，因为不同配置的电脑的cpu算力差距不小，同一个程序在不同电脑上消耗的时间都会不同，这样是无法评定该算法的优劣的。 既然不同电脑处理一个程序所消耗的时间不同，那么处理程序内的一个指令的时间几乎是相等的，因为现在pc算力基本都能达到上亿次每秒，处理一个指令的时间都微乎其微，可以认为相等，这样，我们在评测一个算法的优劣可以通过计算大致要处理指令的个数

表示算法的时间复杂度用大O渐进法表示

推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
 

常见的复杂度有O(1)， O(log)， O(n)， O(nlog)， O(n^2)， O(2^n)， O(n!)

logN，lgN 在程序的算法复杂度中默认都是log2^n

需要注意的是，复杂度往往是取最坏的结果

int test()
{
	int counter = 0;
	for (int i = 0; i < 10000000000; i++)
	{
		counter++;
	}
	return counter;
}
 
//可能会有同学认为上面的时间复杂度应该是O(n)，但结果并非如此
上面的数字尽管很大，但它仍然是一个常数，以cpu的算力来说，它的复杂度就是O(1)
 
 
 
int test(int n)
{
	int counter = 0;
	for (int i = 0; i < n; i++)
	{
		counter++;
	}
	return counter;
}
 
//上面的代码的时间复杂度是O(n)，n的数值并不确定有多大，以最坏的结果为准
 
 
 
 
 
int test(int n, int m)
{
	int counter = 0;
	for (int i = 0; i < n; i++)
	{
		counter++;
	}
 
	for (int i = 0; i < m; i++)
	{
		counter++;
	}
	return counter;
}
	
//上面代码的时间复杂度是O(m+n)
 

时间复杂度的推导靠得是算法的思想，不能看到多少个循环就确定其复杂度了，这样偷懒的想法是不可取的

空间复杂度

空间复杂度指的是一个算法在运行过程中临时占用存储空间大小的亮度，空间复杂度并不是整个程序在运行时占用了多少字节的空间，而是在运行过程中创建的临时变量的个数。需要注意的是函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，空间复杂度是在程序跑起来之后额外向内存申请的空间。

空间复杂度同样是用大O渐进法表示

void BubbleSort(int* a, int n)
{
 
   for (size_t end = n; end > 0; --end)
   {
      int exchange = 0;
      for (size_t i = 1; i < end; ++i)
      {
         if (a[i-1] > a[i])
         {
            Swap(&a[i-1], &a[i]);
            exchange = 1;
         }
      }
 
      if (exchange == 0)
       break;
   }
}
 
//冒泡排序的空间复杂度是O(1)，排序的数组是主程序传过来的，并不是冒泡函数临时申请的，控制循环的两个变量及exchange变量虽然是临时申请的，但过了作用域的块之后就被销毁了，本质上是没有累积创建的，因此该程序只申请了3个变量，是常数个

long long* Fibonacci(size_t n)
{
   if(n==0)
   return NULL;
   long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
   fibArray[0] = 0;
   fibArray[1] = 1;
   
   for (int i = 2; i <= n ; ++i)
   {
     fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
   }
   return fibArray;
}
 
//该例的空间复杂度为O(n)，因为开辟了n+1个额外的空间
 
 

 以上就是评定算法的指标，我们在做题目时，题目可能会要求在给定的时间和空间复杂度下解决，这就考验大家的算法学习成果了，感觉到难是必然的，慢慢耕耘，方得谷粒，接下来我们就正式开始了算法训练