算法复杂度，咕咕咕
1.数据结构与算法
数据结构是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。可以理解为形状不同的容器。
算法是定义好的计算过程，取输入值，经过一系列计算方法变成输出值。
（推荐《数据结构》c或c++版，《算法导论》托马斯，《大话数据结构》程杰）
2.算法效率
复杂度：算法在编写成可执行程序后，运行时要耗费时间与空间资源，即时间复杂度，空间复杂度
时间复杂度主要衡量一个算法的运行快慢，空间复杂度主要衡量算法运行所需的额外空间。
但是在现在计算机的存储容量不断变大，空间复杂度不需要重度关注
3.时间复杂度
描述算法的运行时间，衡量程序的时间效率。（函数式T(N)）
（为什么不去计算程序的运行时间？程序运行时间与编译环境与配置都有关系，不单单是算法。
并且这样的话时间只能再程序写好后测试，而不能在写完前理论计算评估）
T(N)计算了程序的执行次数。算法程序在被编译后生成二进制指令，程序运行就是CPU执行这些编译好的指令。每句指令执行时间基本一样，那么执行次数和运行时间就正相关，脱离具体的编译运行环境，可以代表程序时间效率的优劣。
void func1(int n)
{
int count=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
++count;
}
}
for(int k=0;k<2*n;k++)
{
++count;
int m=10;
while(m--)
{
++count;
}
}T(N)=N^2+2*N+10,对结果影响最大的是n^2，O(n^2)我们实际计算时间复杂度时，计算的也不是程序精确的执行次数，只是计算增长量级，用O的渐进表示法
3.O的渐进表示法
T(N)只保留最高阶项，去掉低阶项。如果最高项存在且不是1，则去掉项的常数系数。如果没有N相关的项目，只有常数项，用1取代加法常熟。
void func2(int n)
{
int count=0;
for(int k=0;k<2*n;k++)
{
++count;
}
int m=10;
while(m--)
{
++count;
}
printf("%d",count);
}
T(N)=2N+10;
O(N)void func3(int n)
{
int count=0;
for(int k=0;k<n;k++)
{
++count;
}
for(int k=0;k<n;k++)
{
++count;
}
printf("%d",count);
}
T(N)=N+M;
O(N)void func4(int n)
{
int count=0;
for(int k=0;k<100;k++)
{
++count;
}
printf("%d",count);
}
T(N)=100;
O(1)const char* strchr(const char* str,int character)
{
const char* p_begin=s;
while(*p_begin!=character)
{
if(*p_begin=='\0')
return NULL;
p_begin++;
}
return p_begin;
}
如果要找的字符在字符串第一个位置，T(N)=1
在最后一个位置，T(N)=N
在中间T(N)=N/2
最好情况O(1),最坏情况O(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;
}
}
}如果数组有序，T(N)=N
有序且为降序，T(N)=N*(N+1)/2
取上界，O(N^2)void func5(int n)
{
int cnt=1;
while(cnt<n)
{
cnt*=2;
}
}
执行次数x,2^x=n
x=logn
O(logn)long long Fac(size_t n)
{
if(0==n) return 1;
return Fac(n-1)*n;
}
调用一次Fac函数的时间复杂度O(1),总共调用n次递归函数，O(n)4.空间复杂度
是一个算法在运行过程中需要额外临时开辟的空间，不是程序要占用多少bytes的空间，算的是变量的个数，用O渐进表示法，函数运行时所需要的栈空间（存储参数，局部变量，一些寄存器信息）在编译期间已经确定，空间复杂度主要通过函数运行时显式申请的额外空间确定
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;
}
}
}
bubblesort额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间，O(1)long long Fac(size_t n)
{
if(n==0)
return 1;
return Fac(n-1)*n;
}
Fac递归调用了n次，额外开辟了n个函数栈帧，每个栈帧使用了常数个空间，O(n)5.常见复杂度对比
6.例题
给定一个整形数组nums,把数组中元素向右轮转k个位置，k为非负数
时间复杂度O(n^2)
void rotate(int *num,int numsize,int k)
{
while(k--)
{
int end=num[numsize-1];
for(int i=numsize-1;i>0;i++)
{
num[i]=num[i-1];
}
num[0]=end;
}
}
循环k次把数组所有元素向后移动一位空间复杂度O(n)
申请新数组，把后k个数据放进新数组，再把剩下的设局挪到数组中
void rotate(int* num,int numsize,int k)
{
int newarr[numsize];
for(int i=0;i<numsize;++i)
{
newarr[(i+k)%numsize]=num[i];
}
for(int i=0;i<numsize;++i)
{
num[i]=newarr[i];
}
}空间复杂度O(1)
前n-k个逆置
后k个逆置
整个逆置
void reverse(int* num,int begin,int end)
{
while(begin<end)
{
int tmp=num[begin];
num[begin]=num[end];
num[end]=tmp;
begin++;
end--;
}
}
void rotate(int* num,int numsize,int k)
{
k=k%numsize;
reverse(num,0,numsize-k-1);
reverse(num,numsize-k,numsize-1);
reverse(num,0,numsize-1);
}/*
void rotate(vector<int>& nums, int k) {k%=nums.size();reverse(nums.begin(),nums.begin()+nums.size()-k);reverse(nums.begin()+nums.size()-k,nums.end());reverse(nums.begin(),nums.end());}
*/