目录
一、数据结构前言
1，数据结构
2，算法
3，数据结构和算法的重要性
二、算法效率
1，复杂度的概念
三、时间复杂度
1，大O 的渐进表示法
2，时间计算例题
四、空间复杂度
1，空间计算例题
一、数据结构前言
1，数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等。
2，算法
算法：就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
3，数据结构和算法的重要性
无论在考研还是在公司面试的时候数据结构都会考到，因此学习数据结构是对应每一个计算机专业学生来说是非常中要的存在。
二、算法效率
1，复杂度的概念
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。就像干活一样，如果有好的办法，又能快速解决又不麻烦的办法，就不会选择有难的又费时的办法。
而时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
三、时间复杂度
时间复杂度是一个代码来衡量的复杂度的其中只有，通常我们定义函数T（N）。
代码展示：
void test(int* N) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { printf("%d ",j); } printf("\n"); } for(int i=0;i<N;i++) { printf("%d ",i); } printf("%d",1); return; }用函数计算时间复杂度T（N）=N^2+N+1
但是代码的时间复杂度是O（N^2）。
1，大O 的渐进表示法
test 执行的代码中：
当N=1 T（N）=1+1+1
当N=10 T（N）=100+10+1
当N=100T（N）=10000+100+1
……
当N=n T（N）=N^2+N+1
当N足够大的时候，影响最大的是N^2 ,而N 和1 的影响几乎微小可以之间、省略不计
所以时间复杂度为O（N）
2，时间计算例题
例题1：
void test(int N) { int count=0; for(int i=0;i<2N;i++) { count++; } for(int i=0;i<10;i++) { count++; } }T（N）=2N+10
O（N）
例题2：
void test(int N,int M) { int count=0; for(int i=0;i<2N;i++) { count++; } for(int i=0;i<M;i++) { count++; } }T(N)=N+M
O(N)
例题3：
void test() { int count=0; for(int i=0;i<100;i++) { count++; } for(int i=0;i<10;i++) { count++; } }T(N)=110
O(1)
例题4：
void test(int N) { int n=1; while(n<N) { n*=2; } }T(N)=log2 N
O(log2 n)
四、空间复杂度
空间复杂度也是用来计算代码复杂度之一，它与时间复杂度类似，但有所不同，例如时间复杂度为O（N），空间复杂度O（1），那么就是 1 个人在时间为 N 做的事情；在相同时间复杂度时，空间复杂度O（N），那么就是 N 个人在时间为 N 做的事情。而这个人就是空间复杂度就是在同时间内要申请的空间大小。
空间复杂度计算时与时间复杂度计算一致的。
1，空间计算例题
冒泡排序：
tpyedef int SLDataType; typedef struct SeqList { SLDataType* arr; int size; int capacity; }SL; void spaw(SLDataType* arr) { SLDataType tmp = *arr; *arr = *(arr + 1); *(arr + 1) = tmp; return; } void SL_bubble_sort(SL* sl)//冒泡排序升序 { for (int i = 0; i < sl->size; i++) { int flag = 1; for (int j = 0; j < sl->size - i - 1; j++) { if (sl->arr[j] > sl->arr[j + 1]) { spaw(&sl->arr[j]); flag = 0; } } if (flag) break; } }那么冒泡排序在时间复杂度为：O（N^2）
以为在函数相同时间内每次只申请了一个（int整形的）tmp
而空间复杂度为O(1)
递归N！：
long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
