前言：内容包括：何为数据结构，时间复杂度及其实例，空间复杂度及其实例
目录
何为数据结构：
时间复杂度：
计算规则：
实例：
空间复杂度：
实例：
何为数据结构：
简单来说，数据结构就是在内存中管理数据，比如增删查改
时间复杂度：
时间复杂度计算的是执行次数
时间复杂度是一个函数
有时某些算法的时间复杂度存在三种情况：最好，平均，最坏
需要以最坏的情况为时间复杂度
计算某个算法的时间复杂度，注重算法思想，不能简单通过循环去判断计算
计算规则：
1 用常数1代表所有为常数次的执行次数
2 只保留最高项
3 若是最高项存在且它前面的常数不为1，则去掉这个不为1的常数
实例：
实例1：计算++count的执行次数
void Func1(int N)
{
int count = 0;
for (int i = 0; i 时间复杂度函数式：F（N） = N*N+2*N+10
时间复杂度：O(N^2)
实例2：计算++count的执行次数
void Func2(int N)
{
int count = 0;
for (int k = 0; k 时间复杂度函数式：F(N) = 2*N+10
时间复杂度：O(N)
实例3：计算++count的执行次数
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k 时间复杂度：O(M+N)
因为M和N的关系不明确，所以不能省略任意一方
实例4：计算++count的执行次数
void Func4(int N)
{
int count = 0;
for (int k = 0; k 时间复杂度：O(1)
O(1)不是代表1次，是代表常数次
实例5：计算冒泡排序的时间复杂度
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 a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}时间复杂度：O(N^2)
冒泡排序的思想：设有N个数字，按照从小到大顺序排序
1 比较N-1次，使得最大的数字来到自己的位置
2 比较N-2次，再使得一个数字来到自己的位置
……
3
2
1
共计：N*(N-1)/2
实例6：计算二分查找的时间复杂度
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin > 1);
if (a[mid] x)
end = mid - 1;
else
return mid;
}
return -1;
}时间复杂度：
二分查找的思想：设有N个数字
一次二分查找使得数字个数减半（区间减半），最坏的情况是经过多次二分查找后，区间缩减至1
设经过了x次二分查找：
1*2*2*2…… = N
即2^x = N，x =
实例7：计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}时间复杂度：O(N)
实例8：计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
if (N 时间复杂度：O(2^N)
空间复杂度：
空间复杂度是临时占用存储空间大小的量度
算的是变量的个数
空间复杂度主要通过申请的额外空间确定
实例：
实例1：计算冒泡排序的空间复杂度
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 a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}空间复杂度：O(1)
冒泡排序额外申请的空间是常数个：end，exchang，i
实例2：计算斐波那契数列的空间复杂度
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 空间复杂度：O(N)
函数内部额外申请的空间个数是N+1个
实例3：计算阶乘Fac的空间复杂度
long long Fac(size_t N)
{
if (N == 0)
return 1;
return Fac(N - 1) * N;
}空间复杂度：O(N)
实例4：计算斐波那契数列的空间复杂度
long long Fib(size_t N)
{
if (N 空间复杂度：O(N)
左边的递归和右边的递归共用同一块空间：当左边的递归调用完成后，它的函数栈帧销毁，归还空间给操作系统，继而调用右边的递归，它的函数栈帧的开辟是原来左边递归所申请的空间
递归空间复杂度的计算主要是看递归的深度
递归中所开辟的最多空间是：n-1
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
