✨✨✨我是分割线✨✨✨

🥝2.3 算法的空间复杂度

---

🍊1.什么是空间复杂度？

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

---

📜案例1——冒泡排序的空间复杂度

空间复杂度计算的是在程序运行过程中，为了满足程序需求，临时创建的空间个数。在下例冒泡排序中，总共开了三个空间，分别是变量end、exchange、i；尽管在这个循环中，exchange这个变量被循环使用，但是用的始终都是exchange这1个空间，只是使用次数在增加，使用的空间个数始终为1，没有发生改变，因此其时间复杂度为O(N)，而空间复杂度为O(1)。

注意：使用了常数个空间==空间复杂度为O(1)

---

📜案例2——斐波那契数列的空间复杂度

下例中，我们单单计算fibArray动态开辟的空间就已经有（n+1）个了，其他剩下的变量开设的都是常数个，因此时间复杂度为O(N)；我们这里只需要算一个大概的即可，计算开辟空间数最多的那个即可。

注意：空间复杂度的计算比时间复杂度的简单，一般来说不是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; }

---

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

long long Fac(size_t N) {     if(N == 0)  return 1;     return Fac(N-1)*N; }

对于本题，递归出N个栈帧，栈帧开辟的空间是常数个，可以认为是O(1)，因此决定其开辟空间个数的主要取决于其递归的次数，本题递归次数为N次，因此空间复杂度为O(N)。

---

📜案例4——计算斐波那契数列的空间复杂度

long long Fib(size_t N) {     if(N < 3)  return 1;      return Fib(N-1) + Fib(N-2);}

上例中我们不断调用，当我们一直递归调用到Fib(2)时，将Fib(2)的值返回给Fib(3)，这时Fib(2)栈帧就销毁了，Fib(3)将接着调用Fib(1)，这时Fib(1)使用了之前Fib(2)使用的空间，使用了同一块空间；同理在向上返回的时候将不断重复使用销毁过的空间，从Fib(2)到Fib(N)总共建立了N-1个栈帧；而后该开始递归调用Fib(N-2)，而这块空间正是之前Fib(N-1)使用过的空间，即空间是可以回收复用的。因此本题的空间复杂度为O(N)。

注意：时间是累计的不可复用，而空间回收之后是可以重复利用的。

程序证明：

当调用完f1( )函数后，将f1中的空间释放；调用f2( )函数，由a和b的地址相同可见，f2( )使用的空间正是刚刚f1释放的空间，证明空间被重复利用了。

void f1(){int a = 0;printf("%p\n", & a);}void f2(){int b = 0;printf("%p\n", & b);}int main(){f1(); //调用函数开始会创建栈帧；结束会销毁栈帧f2();return 0;}

---

📜010.题目难度 ⭐️⭐️

010.下面的说法中，错误的是（ ）。I.算法原地工作的含义是指不需要任何额外的辅助空间II.在相同规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O(2")的算法III.所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界IV.同一个算法，实现语言的级别越高，执行效率越低A.I  B.I、II     C.I、IV     D.III

🍊详细题解：

I. 算法原地工作是指算法所需的辅助空间是常量，即O(1)个空间。

II. 算法的负责度是一个宏观上的理解，O(n)的算法一定是优于O(2")的算法。

III. 时间复杂度总是考虑最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

IV. 越高级的语言，需要层层转换为低级语言给计算机读取，因此执行效率会降低。

✅正确答案：A

 ✨✨✨我是分割线✨✨✨

📝LeetCode之消失的数字

---

---

思路1-排序

思路：将这些数字进行挨个排序，如果后一个数字不是前一个数字+1，那么缺的数就是这两个数共同相邻的那个数。例如我们将数字排序后得到{1,2,4}，我们从前向后挨个比较相邻两个数，我们发现2后面的数字不等于2+1，因此我们得出缺少的数字是3。

优点：简单易想

缺点：时间复杂度太大，以下算法时间复杂度均未满足题目要求。

• 采用冒泡排序—— 时间复杂度：
• 采用快排qsort——时间复杂度：O(N*logN)

---

思路2-映射方式

思路：建立一个可以完整包含0~n的所有整数的数组并将其初始化为全-1；然后将输入的数字x放到对应下标为[x]的数组空间中（如数字6就放到下标为[6]的空间里）；全部放完后，数组中元素值为-1对应的下标，就是缺失的数字。

缺点：这种方式有O(N)的空间复杂度。

---

思路3-异或^

前情提要：

1.异或运算中顺序发生改变，并不会影响最终结果:

 a^b^c = b^a^c = b^c^a = c^b^a =···

2.两个相同数字异或的最终结果为0；

a^a = b^b = 0

3.0和任意非零数x相异或，其结果等于非零数x；

0 ^ x = x

思路：对于本题，可先对0-n的连续数字异或一遍，接着对含有欠缺数字的数组中的每个数字异或，那么该数组中未欠缺的数字和0-n连续数字会异或2次，结果为0；而因为数组中缺少1位数字，原先0-n的连续数字中必有1位只参与异或1次，因此最后异或计算出的值即为缺失的数字。

代码实现：

int missingNumber(int* nums, int numsSize){    int sum=0;    for(int i=0;i<numsSize;++i)    { sum^=nums[i];//计算数列中的异或    }//时间复杂度为O(N) for(int j=0;j<numsSize+1;++j)    { sum^=j;//求0-n的异或    }//时间复杂度为O(N)     return sum;}

---

思路4-数列和相减

（0-n计算等差数列的和）-（数组中的值相加）O(1) O(N) 

优点：算法时间复杂度满足√

代码实现：

int missingNumber(int* nums, int numsSize){    int sum1=0 , sum2=0 ,ret=0;    for(int i=0;i<numsSize;++i)    { sum2+=nums[i];//计算数列中的和    }//时间复杂度为O(N)    sum1=numsSize*(numsSize+1)/2;//计算0-n的等差数列之和    ret=sum1-sum2;    return ret;}

 ✨✨✨我是分割线✨✨✨

📝LeetCode之旋转数组

---

进阶：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

---

思路1-依次右移动

思路：右旋K次，依次移动一个；当K=N时，等于数组没有发生旋转，当K=N+1时，等于数组旋转1次，即旋转的次数=(K%N)；当（K%N=N-1）时，旋转的次数最多。

时间复杂度：旋转1次需要移动N次，旋转K次就需要移动N*K次，因此为O(K*N)；当K的值为N-1时，复杂度为O(N^2)，但是由于K也是未知数，因此该算法的时间复杂度为O(N*K)。

空间复杂度：没有额外开数组，用的是原数组，因此为O(1)。

---

思路2-额外开数组

思路：用空间来换时间，额外建立一个数组，将后K个数拷贝到新建数组的前端，将(n-K)个剩下的数，拷贝到新数组的后端。

时间复杂度：将从前向后挨个计算，将前(n-k)个数拷贝到新数组后(n-k)个位置，再将后k个数拷贝到新数组的前k个位置，计算量即为n，因此时间复杂度为O(N)。

空间复杂度：这时额外开了一个数组，因此空间复杂度为O(N)。

---

思路3-三轮逆置

思路：用空间来换时间，额外建立一个数组，将后K个数拷贝到新建数组的前端，将(n-K)个剩下的数，拷贝到新数组的后端。

时间复杂度：进行三轮逆置，因此时间复杂度的量级依然取决于元素个数n，时间复杂度为O(N)。

空间复杂度：没有额外开数组，用的是原数组，因此为O(1)。

代码实现：

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=k%numsSize;    reverse(nums,0,numsSize-k-1);//step1.逆置前n-k个    reverse(nums,numsSize-k,numsSize-1);//step2.逆置后k个    reverse(nums,0,numsSize-1);//step3.逆置整体n个}

 ✨✨✨我是分割线✨✨✨

📜水滴石穿

---

📜011.题目难度 ⭐️

011.以下算法的时间复杂度为（ ）。void fun(int n) {int i = 1;while (i <= n)i = i * 2;}A.O(n) B.O(n^2) C.O(nlogn) D.O(logn)

🍊详细题解：

✅正确答案：D

---

📜012.题目难度 ⭐️

012.以下算法的时间复杂度为（ ）。void fun(int n) {int i = 0;while (i * i * i <= n)i++;}A.O(n) B.O(nlogn) C.O(³√n) D.O(√n)

🍊详细题解：

✅正确答案：C

---

📜013.题目难度 ⭐️

013.以下算法中最后一行语句的执行次数为（ ）。int m = 0, i, j;for (i = 1; i <= n; i++)for (j = 1; j <= 2 * i; j++)m++;A.n(n+1) B.n C.n+1 D.n^2

🍊详细题解：

✅正确答案：A

---

📜014.题目难度 ⭐️⭐️

014.程序段如下：for (i=n-1;i>1;i--)for (j=1;j A[j+1])A[j]与A[j+1]对换;其中n为正整数，则最后一行语句的频度在最坏情况下是（ ）。A.O(n) B.O(nlogn) C.O(n³) D.O(n²)

🍊详细题解：

✅正确答案：D

---

📜015.题目难度 ⭐️⭐️

015.【2014统考真题】下列程序段的时间复杂度是（ ）。count=0;for (k=1 ; k<=n ; k*=2)    for(j=1;j<=n;j++) count++;A.O(logn) B.O(n) C.O(nlogn) D.O(n^2)

🍊详细题解：

✅正确答案：C

---

📜016.题目难度 ⭐️⭐️⭐️

016.【2017统考真题】下列函数的时间复杂度是（ ）。    int func(int n){ int i=0,sum=0; while (sum<n) sum +=++i; return i;    }A.O(logn) B.O(√n) C.O(n) D.O(nlogn)

🍊详细题解：

✅正确答案：B

---

 📜017.题目难度 ⭐️⭐️⭐️

🍊详细题解：