空间复杂度

空间复杂度概念：

和时间复杂度一样，时对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间，因为这也没什么意义，所以空间复杂度算的是变量的个数，也使用大O监禁表示法。

void BubbleSort(int * a,in 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;

}

}

答案O(1)

解析：

这里其实总共开辟了三个空间，分别为end.exchange,i;

既然时常数个变量，那么空间复杂度就是O(1)，空间复杂度算的时申请的额外空间

苏哦提跟上面的int *a和int n没有关系。

可能有人觉得这个for循环，exchange应该开辟n次，其实每次循环进来，exchange 都会重新开辟，结束一次循环exchange销毁，以此类推，exchange始终时同一个空间。

什么时候会出现O(n)呢？