// 1.计算BubbleSort的空间复杂度？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;}
}

提问:

                        当时我在计算该程序的空间复杂度，有个疑问，为什么不把数组算进去

                        这是因为，我们在计算之前，就已经开辟了数组的栈帧空间，开始前就给出了，所以不用在空间复杂度内加上数组的大小

案例2:计算斐波那契额数列的前N项的空间复杂度

//计算斐波那契额数列的前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;
}

        分析:

                我们当前的变量为0，但是我们要求第N项的空间复杂度，所以我们开辟了n+1块空间，用来计算前N项和的空间复杂度，O(N+1)为其空间复杂度，但是大O的渐进表示法，我们计算出斐波那契额数列前N项和的空间复杂度为O(N)

 案例3:计算阶乘递归Fac的空间复杂度？

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

案例4:F1和F2两函数是否使用的同一块空间

//F1和F2两函数是否使用的同一块空间
void F2()
{int b = 0;printf("%p\n",&b);
}
void F1()
{int a = 0;printf("%p\n",&a);
}int main()
{F1();F2();return 0;
}

 提问:

        那如何修改，才能使两个函数指向不同栈帧空间？

分析:

       当我们在F1中调用F2时，使得F1函数无法释放栈帧空间，F2就必须在F1低地址处压栈，此时他们两个维护的栈帧空间则不相同

图解：

案例5:计算该程序的空间复杂度

//计算该程序的空间复杂度
long long Fib(size_t N)
{if (N<3){return 1;}return Fib(N-1) - Fib(N-2);
}

                注:时间一去不复返无法重复利用，但是空间用了之后归还，可以重复利用

案例6:经典OJ(难度中等)

          示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

        示例 2:

void reverse(int* nums,int begin ,int end)
{while (begin < end){int tmp = nums[begin];nums[begin] = nums[end];nums[end] = tmp;begin++;end--;}}
void rotate(int* nums, int numsSize, int k)
{if (k > numsSize){k %= numsSize;}reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums, 0, numsSize - 1);
}