判断斐波那契递归的时间复杂度和空间复杂度以及例题

🐖前言

⭐什么是斐波那契数列？

斐波那契数列(Fibonacci sequence)，又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
这个数列从第3项开始，每一项都等于前两项之和。

🐖斐波那契怎么用递归写出来？

代码如下

#include
int fun(int n)
{
	if (n == 1 || n ==2)
		return 1;
	else
	{
		return fun(n - 1) + fun(n - 2);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fun(n);
	printf("%d\n", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

🐕斐波那契递归的时间复杂度

答案:O($2^N$),那么是为什么呢，首先我们知道在进入一次这个函数所进行的次数是常数次，所以我们只要知道调用了几次函数我们就知道了他的时间复杂度了。下面我们画图解释。

而对于这个等比数列相加，我们可以通过大O的渐进表示法，很容易的知道他的时间复杂度是O($2^N$).

🐕斐波那契递归的空间复杂度

答案：O(N),大家想一下是为什么呢？
对于时间复杂度来说，时间是叠加的不可以重复利用，但是对于空间来说，他是可以重复利用的，而对于一次斐波那契的递归就是从n到1，开辟n个空间，在进行一次时，用的空间还是上面开辟的空间，所以他的空间复杂度是O(N).

🐖时间复杂度和空间复杂度例题

🐕例题1消失的数字

![在这里插入图片描述](https://img-blog.csdnimg.cn/0fe357fb6ce34dab8f1da54fe42f1b6a.png

先考虑思路，然后再写代码。这是我们写代码必须具备的东西。
🍔思路一：将从0~N相加再减去数组nums中的数所剩余的数就是缺失的整数。
⭐ 那么他的时间复杂度是多少了，看他运算了多少次从0开始相加到N，进行了N次，再减去nums也是N次，所以时间复杂度就是O(N).
⭐那么再想一想他的空间复杂度是多少，额外申请的空间 也就是n了所以空间复杂度就是O(1)
🍔思路二：按位异或(^),首先我们知道自己和自己异或等于0，有了这个知识，可以将0~N，全部跟nums异或，最后剩余的那个就是缺失的数字。
⭐那么他的时间复杂度是多少，对于这个从0异或到N，说明他的时间复杂度就是O(N),对于空间来说又没有额外申请空间所以空间复杂度是O(1).

🍔思路一

看下面代码

int missingNumber(int* nums, int numsSize){
    int i=0;
    int sum=0;
    //求和
    for(i=0;i<numsSize+1;i++)
    {
        sum+=i;
    }
    //减去数组的内容
    for(i=0;i<numsSize;i++)
    {
        sum-=nums[i];
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍔思路二

请看下面代码

int missingNumber(int* nums, int numsSize){
    int i=0;
    int ret=0;
    for(i=0;i<numsSize+1;i++)
    {
        ret^=i;
    }
    for(i=0;i<numsSize;i++)
    {
        ret^=nums[i];
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

🐕例题2轮转数组

🍔思路1：，将最后一个数字拿出来，然后将其他数字依次向后退一个，最后再将最后一个数字放再第一个，轮转几次就重复几次操作。
⭐思考时间复杂度：假设轮转N次，而每一次都要进行M次操作，所以他的时间复杂度就是O(N*M),可以理解成O($N^2$),那么空间复杂度是O(1)，因为没有额外申请空间。

注意：再用这个思路编译时，好像过不去，其实是时间复杂度太大，效率太低，请看代码

void rotate(int* nums, int numsSize, int k){
       while(k--)
    {
        int ret=nums[numsSize-1];
        int right=numsSize-1;
        int left =0;
        while(right)
        {
            right--;
             nums[right+1]=nums[right];
        }
       nums[left]=ret;
       left++;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🍔思路二：第二个思路是最重要的，以空间换取时间，创建一个新的数组，将需要旋转的数字全部放到前面，不需要旋转的数组放到后面，随后将该数组拷贝回原数组
⭐时间复杂度：O(N),空间复杂度就是O(N).

思路三：三步翻转法，这个思路看看就行了，不太好想，看图.
时间复杂度O(N)
空间复杂度O(1)

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

void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    //逆置前n-k个
    reverse(nums,0,numsSize-k-1);
    //逆置后k个
    reverse(nums,numsSize-k,numsSize-1);
    //全部逆置
    reverse(nums,0,numsSize-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🐖总结

这里只是我认为对于新手练习时间复杂度和空间复杂度重要的东西，当然这只是九牛一毛，还是希望大家多多练习，相信大家一定可以拿下这块肥肉加油😊😊