在正式进入数据结构的学习过程前先来了解一下复杂度的概念。

时间复杂度

（1）
定义：算法的复杂度是一个函数（指数学中），定量描述了算法的运行时间，但是每个算法在不同配置的机器上运行时间又有所差异，所以把算法中基本操作的执行次数定义为时间复杂度。
（2）大O渐进表示法： 大O符号：用于描述函数渐进行为的数学符号 推导大O阶的方法：
1.用常数1取代运行时间中所有的加法常数。
2.函数中只保留最高阶项。
3.若最高阶项存在且不为常数，则保留本身去掉与其相乘的常数。

这里表示O(N^2)，可以看出N代表的是代入函数后结果的量级，而不是具体值

我们可以发现大O渐进表示法去掉了对结果影响不大的项

（3）另外有些算法的时间复杂度存在最好、平均和最坏的情况。
最坏情况：任意输入规模的最大运行次数
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数

在实际情况中一般关注算法的最坏情况，这样运行的时候要么达到预期要么有惊喜
接下来看几个经典例子
1.二分查找（前提：数组有序）

我们可以看到O(LOG^2N)非常高效，但受限于前提条件，所以实际使用上还差强人意，但后面我们可以学到红黑树来表示这种时间复杂度。

还有一个小细节，常用logN来表示以二为底的对数，有些地方会lg(不推荐），其它底数用log……XN来表示（底数不好打出来）

2.递归函数

斐波那契：

（4）常见复杂度对比

空间复杂度

• 定义：一个数学表达式，是对一个算法在运行过程中临时占用存储空间的量度。同样用大O渐进法表示。

• 注意：函数运行时所需要的栈空间（存储参数、局部变量、寄存器信息）在编译区间已经确定好，因此空间复杂度主要通过函数运行时额外申请的空间来确定。

• 典型例题
  
  通过malloc函数动态开辟了一块大小与输入n大小成正比的内存空间，即为n的线性函数，所以n就是临时占用存储空间的量度

• 
  每次递归调用都会开辟一块与n成线性关系大小的空间，累加起来运用大O渐进表示法保留n得到空间复杂度

• 重要辨析
  
  main函数中调用分先后，先调用F1开辟一块内存空间，使用完后将使用权还给操作系统，再调用F2时可以继续使用这块空间。
  内存的申请就像住酒店，你住完后还给酒店，下一个人还可以继续住。

• 
  此时F1F2不在同一函数内，分开调用所以使用不同空间。

• 斐波那契调用

• 
  该函数会先调用n-1，n-1会调用n-2、n-3，优先n-2，所以调用的优先顺序是n、n-1、n-2、n-3等，再每一次返回的过程完成时再调用同时调用优先级低的一方，因为二者在同一函数内，所以使用内存空间相同。