在学习数据结构前，我们需要了解时间复杂度和空间复杂度的概念，这能够帮助我们了解数据结构。
算法效率分为时间效率和空间效率
时间复杂度
一个算法的复杂度与其执行的次数成正比。算法中执行基础操作的次数，为算法的时间复杂度。
我们采用大O的渐进表示法。
推导大O阶方法:
1用常数1取代运行时间中的所有加法常数
2在修改后的运行次数函数中，保留最高阶项。
3如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
在实际中一般情况关注的是算法的最坏运行情况
举例：
冒泡排序的时间复杂度
从这个例子我们知道了，不是一层循环时间复杂度就是N，两层就是N^2要看具体算法实现。
二分法时间复杂度分析：
阶乘递归的时间复杂度
空间复杂度
对临时储存空间占用大小的量度。计算的是变量的个数。
首先来看冒泡排序的时间复杂度
循环走了N次，重复利用的是一个空间。
斐波那契数列的空间复杂度：
阶乘的时间复杂度： 
算法题
消失的数字
面试题 17.04. 消失的数字 - 力扣（LeetCode）
思路1：
排序，如果后一个数字不等于前一个数字加1，那么前一个数字加1，就是要寻找的消失的数字。
这种方法的时间复杂度是N*lgN
思路2：
把0到N加起来，再减去各个数字，得到的数字就是消失的数字。这里的时间复杂度是O（N）。如果先累加，时间复杂度是0(N),依次遍历一遍为O(N)。
int missingNumber(int* nums, int numsSize){ int N=numsSize; int ret=(0+N)*(N+1)/2; for(int i=0;i<numsSize;++i) { ret-=nums[i]; } return ret; }
思路3：
把数组中的所有数字跟0到N异或，剩下的数字就是消失的数字。（我们知道，x^x=0,0^x=x）
int missingNumber(int* nums, int numsSize){ int N=numsSize; int x=0; for(int i=0;i<numsSize;i++) { x^=nums[i];//x将包含数组nums中所有元素的异或结果 } for(int j=0;j<=N;j++) { x^=j; } return x; }
思路1：旋转k次
void rotate(int* nums, int numsSize, int k) { //首先把最后一个数储存起来 for(int i=0;i<k;i++) { int tmp=nums[numsSize-1]; for(int i=numsSize-2;i>=0;i--) { nums[i+1]=nums[i]; } nums[0]=tmp; } }
思路2：三段逆置
前k个逆置
后k个逆置
再整体逆置
void Reverse(int*nums,int left,int right) { while(left<right) { int tmp=nums[left]; nums[left]=nums[right]; nums[right]=tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { if(k>=numsSize) { k%=numsSize; } Reverse(nums,numsSize-k,numsSize-1); Reverse(nums,0,numsSize-k-1); Reverse(nums,0,numsSize-1); }
思路3：
以空间换时间
void _rotate(int*nums,int numsSize,int k,int*tmp) { k%=numsSize; int n=numsSize; memcpy(tmp,nums+n-k,sizeof(int)*k);//将数组最后 k 个元素复制到 tmp 数组的前 k 个位置 memcpy(tmp+k,nums,sizeof(int)*(n-k));//将数组的前 (n-k) 个元素复制到 tmp 数组的剩余位置 memcpy(nums,tmp,sizeof(int)*(n));// // 将 tmp 数组的内容复制回 nums 数组 } void rotate(int* nums, int numsSize, int k) { int tmp[numsSize]; _rotate(nums,numsSize,k,tmp); }
