在学习数据结构之前，我么先明白一下数据结构与算法是什么，他们之间有什么关系。

1.什么是数据结构

在内存中帮助我们管理数据，以一种组织如树形结构，链式结构，图型结构，通过增删查改等功能管理数据。

2.什么是算法

定义良好的计算过程，取一个或一组值输入，并产生一个或已组织作为输出，简单来说就是一系列算法的计算步骤，将输入数据转化为输出结果。

对于算法来说，数据结构本身就是一种算法。

3 算法的时间复杂度与空间复杂度

如何衡量一个算法的好坏？

我们用算法的都组读取表述一个算法的运行效率与空间占比，这也是一个算法好坏的判别一句。

1.算法的复杂度

算法在编写成可执行程序后，运行所耗费的时间资源与空间资源。因此衡量一个算法的好坏，一般是从时间复杂度与空间复杂度两个维度去衡量

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所消耗额外空间。在早期计算机内存容量小，所以对空间复杂度很在乎，但如今我们不需要特别关注一个算法的空间按复杂度。

2.时间复杂度

总结下来就是某条基本语句与问题规模N之间的数学表式，就是计算该算法的时间复杂度。

先举一个例子说明时间复杂度的计算是一种估略计算。

N                 约为

1002            1000

105465        100000

10545634    100000000

对一个数N，N越大，后面尾数的对结果的影响越小。

那我们再来看看对于一个代码，他的执行次数呢？

//计算一下FUN1中++cout语句执行了多少次
void FUN1(int N)
{
  int count = 0;
  for (int n = 0; n < N*N; n++)
  {
    ++count;
  }
  for (int n = 0; n < N*2; n++)
  {
    ++count;
  }
    #define x 10
  for (int n = 0; n < x; n++)
  {
    ++count;
  }
  printf("%d", count);
}

对于以上的函数我们可以计算他的时间复杂度函数，即++count程序运行了多少次。

时间复杂度函数为F（N）=N*N+2*N+10;  

但在实际过程中我们只是识别它复杂度的级别，并不去关注更详细的复杂度。只需要大概执行次数，这里就会使用一个大O的渐进表示法

即只看它的幂次项最高的那一项，整体的大小由他绝定，当然我们也不关注最高项的系数。

如上，N*N最大，FUN1的时间复杂度为O（N^2），这是一种估算的表示方法。

总结如何推导大O的渐进表示法

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

明白了时间复杂度是什莫我们再来看看几个例子：

//再举例
void FUN2(int N)
{
  int count = 0;
  for (int k = 0; k < 2 * N; k++)
  {
    count++;
  }
  int M = 10;
  while (M--)
  {
    count++;
  }
  printf("%d", count);
}
//时间复杂度为O（N）

这里的执行次数为2N+0，即表示为O（N）。

void FUN3(int m,int n)
{
  int count = 0;
  for (int m = 0; m < 100; m++)
  {
    ++count;
  }
  int count = 0;
  for (int n = 0; n < 100; n++)
  {
    ++count;
  }
  printf("%d", count);
}

这里的时间复杂度中，执行的次数为m+n次，之乐的m与n都是一次幂，且并未表示m与n的大小关系，所以这里就是O（m+n），若有条件则为m>>n,则就是O（m）

再比如：

void FUN4(int N)
{
  int count = 0;
  for (int k = 0; k < 100; k++)
  {
    ++count;
  }
  printf("%d", count);
}

这里执行的次数为100，对于常数，时间复杂度都为O(1)，这里的常数可能会很大，但对于计算机来说，所需要计算的时间是一样的，基本是一样。所以对于常数时间复杂度为O（1）。

就像面对一个地球，我们要有相对于有银河系这样的眼界，即使地球与其他星球有差异 ，但对于银河系来说，轻如鸿毛。这里的常数对于CPU来说，也是如此。

另外有些算法的时间复杂度存在最好、平均和最坏情况：

比方说查找一组数中与已给出的数：const char *strchr(const char *str,int chracter),

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

在这里查找的情况有：

最好情况：1次找到

最坏情况：N次找到

平均情况：N / 2次找到

在实际中一般情况关注的是算法的最坏运行情况，查找最多要N次，所以数组中搜索数据时间复杂度为O(N)，时间复杂度是降低预期，做最坏的打算。

对于一些算法的时间复杂度：

void BubbleSort(int* a, int n)
{
  assert(a);
  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（N^2）

计算冒泡排序的时间复杂度

int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;
  int end = n - 1;
  while (begin <= end)
  {
    int mid = begin + ((end - begin) >> 1);
    if (a[mid] < x)
      begin = mid + 1;
    else if (a[mid] > x)
      end = mid - 1;
    else
      return mid;
  }
  return -1;
}

最坏情况：执行次数为2为底，N的对数。即O（log2 N）

计算阶乘递归Fac的时间复杂度

long long Fac(size_t N)
{
  if (0 == N)
    return 1;
  return Fac(N - 1) * N;
}//O(N)

递归了N次。时间复杂度为O（N）。

计算斐波那契递归Fib的时间复杂度

long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2)
}
//O(2^N)

对于该函数我们画图分析：

该递归是一个以2为公比的等比数列，时间复杂度为O(2^N)。

3.空间复杂度

空间复杂度也是一个数学表达，是对一个算法在运行过程中 临时占用存储空间大小的量度 。

从这句话我们就可以理解出来，对于空间复杂度，看的是空间的占比多少，空间的占比大小就取决于所创建的变量多少，以及变量的大小，因为在创建变量时内存需要为其开辟空间。

但是我们还需要要注意的是：

空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以 空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使用 大 O 渐进表示法 。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因

此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

实例1：

计算BubbleSort的空间复杂度？
void BubbleSort(int *a, int n){
     assert(a);
    for (size_tend=n; end>0; --end)
   {
     intexchange=0;
    for (size_ti=1; i<end; ++i)
      {
        if (a[i-1] >a[i])
          {
           Swap(&a[i-1], &a[i]);
            exchange=1;
          }
       }
      if (exchange==0)
          break;
    }
}

实例 1函数中只有几个定义的变量， 使用了常数个额外空间，所以空间复杂度为 O(1)

实例2：

计算 Fibonacci 的空间复杂度？

 返回斐波那契数列的前 n 项

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;
}

实例 2 动态开辟了 N 个空间，空间复杂度为 O(N)

实例3：

// 计算阶乘递归Fac的空间复杂度？

long longFac(size_tN)
{
   if(N==0)
   {return  1;}
   return  Fac(N-1)*N;
}

实例 3，对于函数来说，每调用一次，就要为它开辟一次函数栈帧， 递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)

4. 常见复杂度对比

一般算法常见的复杂度如下：

画出它们的函数图像我们就可以清楚的认识到他们对应复杂度的变化