21天学算法系列（1）

• • 算法效率
  • • 时间复杂度和空间复杂度
    • • 时间复杂度的计算
      • 空间复杂度的计算
  • 数学知识
  • • 幂
    • 对数
    • 等差数列
    • 等比数列
    • 斐波那契数列

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

首先学习算法就是了解什么是算法。我们经常在一些书上可以看到说：“程序就是数据结构+算法”数据结构就是我们用来存储数据的不同形式，比如线性表和非线性表，线性表有很多比如：如果需要排序数据并且随机访问就使用顺序表，如果需要数据经常的插入删除并且减少空间浪费，随时需要空间就开辟就可以使用双向带头循环链表。非线性表有很多比如二叉树等等。用途广泛，必须根据你的需要自行选择。
既然数据的存储已经完成了，那么我们就需要对数据进行相应的处理，这时候使用的就是算法了。算法的种类更是数不胜数。许许多多的算法对应着相应的问题。所以现在我们就来用21天打卡算法的学习。对算法有一个初步的认识。
这21天内学到的所有算法会依次记录在博客中，那么就从今天开始一起进入算法的殿堂吧。

首先谈到算法就不得不说到算法的效率，评鉴一个算法的好坏第一方面就是评定这个算法的效率如何，而算法的效率并不是用这个算法一共跑了多少时间来决定的。因为在不同的电脑上，因为配置的不同，时间的差别往往会很大。所以这里引入了时间复杂度。来评鉴算法执行的快慢
在早期的计算机中，一般存储空间都是比较小的，所以又引入了算法的另一个效率，那就是空间效率，就是说这个算法在完成这些目标数据处理的过程中使用了多少的额外空间，注意是额外空间。由此引入了空间复杂度。

时间复杂度是一个衡量算法时间的相对标准。他不是一个固定的时间例如多少分多少秒，而是一个大概的估计数值。比如同一个算法在不同的机器上运行的时间肯定不同。这时候就需要我们的时间复杂度来衡量算法的时间效率。

时间复杂度通常使用大O的渐进表示法（空间复杂度也是）

那么什么是大O的渐进表示法呢？

列举几个实例给搭建看看 O(N),O(N^2),O(1);

如上所示就是大O的渐进表示法。括号内就是算法执行的次数估计值，要记住时间复杂度计算的是执行次数
但是他不是一个准确的数字而是一个估计值，比如(N^2+2N+10)在N很大的时候除了最高次项其他的都可以忽略不计，这类似与数学中的极限思想，只保留对结果影响最大的一项。

推导法则如下：
1.若括号内是常数都写成O(1)
2.若是括号内是多项式例如O(N^2+3n+9)则只保留最高次项
3.若是最高次项的系数不为1则统一写成1

上文提到，时间复杂度实际上就是计算代码执行次数
而空间复杂度实际上就是计算变量个数

这里需要我们先记住一句话时间是累积的空间是不累积的。

意思就是时间是一去就不会回来的，但是空间不会，空间会一直存在于这里，无论如何只要这块空间空下来，那么这个空间就可以再重复使用。

学习算法肯定离不开数学，所以在进入算法之前需要我们了解一下基本的数学知识

幂的知识就是指数运算，比如：4的a次方，这种就属于是幂运算，在C语言中我们可以使用一个pow的库函数来完成幂运算。

对数就是平常看到的log样子的数学式，对数有一个定义：若t=n的m次方，那么log_nt = m;在C语言中同样有一个库函数log2( )，比如log2( t )就是用来计算以2为底，t为指数的对数式，同时对数这里也有一个换底公式。

所以其他底数的对数运算就可以统一都变成以2为底数的两个对数相除。

等差数列就是每个数后一个减掉前一个得到的差值都是相同的d，这个差值d就是公差。
等差数列的求和公式：Sn=(a1+an)n/2 ；Sn=na1+n*(n-1)*d/2（d为公差）

等比数列的后一个都是前一个数的q倍，这个q就是公比
递推公式：

等比数列求和公式：Sn=na₁(q=1)
Sn=a₁(1-q^n)/(1-q) =(a₁-anq)/(1-q) （q不等于 1）

除了第0个和第一个数之外，其他的数都是等于前两个数之和
递推公式：

求斐波那契数列有两种方法，一种就是使用递归，零一种就是用循环。一般求斐波那契数都是使用循环，因为如果不考虑溢出问题，循环的效率式很高的。递归进行了太多的重复计算，一般到了第50几个斐波那契数就需要计算很长时间了。

基本的几个数学知识就先到这里，其次还需要了解的是矩阵（线性代数）这里放到下一个文再说。第一天的算法学习就到这里