1.什么是时间复杂度和空间复杂度？
1.1算法效率
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称为空间复杂度。
时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的水准，所以我们如今不需要再特别关注算法的空间复杂度。
1.2时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法度上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
1.3空间复杂度的概念
空间复杂度是对一个算法运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少比特位的空间，因为这个也没有太大的意义，所以空间复杂度算的是变量的个数。空间复杂度计算也采用大O渐进表示法。
2.什么是大O 渐进表示法？
实际中我们计算时间复杂度时，我们其实并不一定要精确的执行次数，而只需要大概执行次数，那么这里我们使用大O渐进表示法
大O符号（Big O notation）：是用来描述函数渐进行为的数学符号。
推导大O阶方法：
1.用常数1取代运行时间中所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
3.如何计算常见算法的时间复杂度和空间复杂度？
3.1普通常见的时间复杂度计算
3.1.1Func1
void Func1 (int N)
{
int count=0;
for(int j=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;
}
printf("%d ",count);
}
3.1.2Func2
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);
}
3.1.3Func3
void Func3 (int N,int M)
{
int count=0;
for(int k=0;k<N;++k)
{
++count;
}
for(int k=0;k<M;++k)
{
++count;
}
printf("%d ",count);
}
3.1.4Func4
void Func4 (int N)
{
int count=0;
for(int k=0;k<100;++k)
{
++count;
}
printf("%d ",count);
}
3.2存在时间复杂度最好、平均、最坏的情景
const char * strchr (const char * str,char character)
{
while(*str!='\0')
{
if(*str==character)
return str;
str++;
}
return NULL;
}
3.3冒泡排序的时间复杂度计算
void Bubblesort(int *a ,int n)
{
assert(a);
int exchange=0;
for(size_t end=n;end>0;--end)
{
for(size_t i=1;i<end; ++i)
{
if(a[i-1]>a[i])
{
int tmp=a[i-1];
a[i-1]=a[i];
a[i]=tmp;
exchange=1;
}
}
if (exchange==0)
break;
}
}
3.4折半查找的时间复杂度计算
//前提数组中数据为升序
int BinarySearch(int *a,int n,int x)
{
assert(a);
int left=0;
int right=n;
while(left<right)
{
int mid=(left+right)/2;
if(a[mid]<x)
{
left=mid;
}
if eles (a[mid]>x)
{
right=mid;
}
else(a[mid]==x)
return mid;
}
}
3.5计算阶乘递归的时间复杂度
long long Factorial(size_t N)
{
return N<2?N:Factorial(N-1)*N;
}
4.常见的时间复杂度：
结论：O（1）<O(log n)<O(n)<O(n log n)<O(n^2)
5.空间复杂度的计算
5.1 空间复杂度为O（1）
时间虽然是累计的，但是空间不累计，循环走了N次，但始终重复利用的是一个空间
void Bubblesort(int *a ,int n)
{
assert(a);
int exchange=0;
for(size_t end=n;end>0;--end)
{
for(size_t i=1;i<end; ++i)
{
if(a[i-1]>a[i])
{
int tmp=a[i-1];
a[i-1]=a[i];
a[i]=tmp;
exchange=1;
}
}
if (exchange==0)
break;
}
}
5.2空间复杂度为O（n）
5.2.1由动态内存开辟的
void factor(int *a)
{
int * a=(int)malloc((n)*sizeof(int));
}
5.2.2函数递归类型
递归调用了N层，每次调用建立了一个栈帧，每个栈帧使用了常数个空间——》O(1)
调用时，建立栈帧
返回时，销毁
最后对未知的N 空间复杂度为O（N）