[数据结构与算法]3.7空间复杂度

 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;
   }
}

使用了常数个额为空间，空间复杂度O(1)

?后者函数中开辟了常数个内存，空间复杂度O（1），前者O（N）

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
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 <= n ; ++i) {
		fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
	}
	return fibArray;
}

?采用动态内存开辟，空间复杂度O(N)。

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N) {
	if(N == 0)
		return 1;

	return Fac(N-1)*N;
}

?实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N) {
	if(N < 3)
		return 1;

	return Fib(N-1) + Fib(N-2);
}

?空间复杂度O(N)

?若空间复杂度为O(2^N)，见下列程序

?取10000时已经栈溢出，说明空间复杂度不是指数大小

?

?时间是累计的，一去不复返了，空间是可销毁了，可重复利用的

?算Fib（N-1）时，递归到最后一层是Fib（2）用完后栈帧销毁，Fib（1）覆盖之前的空间。

?列如下列程序

void f1()
{
	int a = 0;
	printf("%p",&a);
}
void f2()
{
	int b = 0;
	printf("%p\n",&b);
}
int main()
{
	f1();
	f2();
	return 0;
}

?

?f1()和f2()地址相同，用同一份空间

?

?1.右旋k次，依次移动一个（leetcode不通过）

时间复杂度：O(N*K) 旋转一次是O(N)，旋转K次。K最大取N-1，K=N时不旋转

最坏情况 k%N=N-1时 时间复杂度O(N*N)

空间复杂度：O(1)，没有额外开辟数组

2.额外开辟数组，后K个放在前面

3. 三趟逆置

?

void reverse(int*a,int left,int right)
{
    while(left<right)
    {
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        ++left;
        --right;
    }
}


void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);


}

?

?