实例五（阶乘递归）

long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

递归了N次，所以时间复杂度为：O(N)

实例六(斐波那契数列)

long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

递归的算法 = 递归的次数*每次递归调用的次数

这里每次递归调用的次数为0(1), 所以就算递归次数就行了

有图可以看到，次数= 2^0 + 2^1 + 2^2 + 2^3 …+ 2^n-1 - x(因为由图，越往后Fib()中的值越小， 而右边Fib()中的值比左边的小，右边Fib()中个的值肯定先被减为0，所以就要减去x ,这多算的部分)

—> x太小可以忽略不计， ----> 2^n - 1 - x - 1

由于1和x远小于 2^n - 1,所以忽略不计

则：O(2^N)

空间复杂度介绍

空间复杂度：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，我们也是使用大O的渐进表示法。

两者的关系比较

时间一去不复返的，空间是可以重复利用的，空间复杂度算的是临时占用内存（额外的）

实例

实例一（冒泡排序）

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)

实例二(阶乘)``

long long Factorial(size_t N)
{
 return N < 2 ? N : Factorial(N-1)*N;
}

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

剑指offer

消失的数字

链接：消失的数字OJ链接

题目要求是在O(n)的时间内完成，这里我们可以看到，对时间提出了要求。

算法一：用完整的数组减去残缺的数组 = 得到缺失的数字

即------> (0 + 1 +2 +3 + 4 +5 + 6 + …n) - (a[0] + a[1] + a[2] + a[3] + a[4] +…+ a[n])

算法一：空间复杂度为O(1), 时间复杂度为O(n)

算法二：运用异或的思想

异或（^）: 两个相同数异或，结果为0

0与任何数异或，结果为任何数

1与任何数异或， 都为1

第一步，设x = 0，让x与 [0, n] 这个区间的所有数异或，

------> 0 ^ 0 ^ 1^ 2 ^ 3^ 4^ 5^6 ^…n

第二步，再让x 与数组中的每个值异或，

------> 0 ^ 0 ^ 1^ 2 ^ 3^ 4 ^ 5^6 ^…n ^ 0 ^ 1^ 2 ^ 3^ 4^ 5^6 ^…n - 1

(相同的，出现2次的便异或消掉了，剩下的就是出现一次的)

--------> 0 ^ 缺失的数字 = 缺失的数字

最后， x = 缺失的数字

算法二：空间复杂度O(1), 时间复杂度O(n)

算法一很简单，这里，我来介绍算法二。

int missingNumber(int* nums, int numsSize)
{
    int x = 0;
    for(int i = 0; i <= numsSize; i++) // x与[0, n]异或
    {
        x ^= i;
    }
    for(int i = 0; i < numsSize; i++)  // x在与数组上的每个数异或，出现2次的为0
    {
        x ^= nums[i];
    }
    return x;
}

轮转数组问题

链接： 轮转数组OJ链接

思路一：暴力求解，旋转k次

时间复杂度O(N*k), 空间复杂度O(N)

思路二：开辟一个空间，用另一个数组

如图，让nums这个数组旋转3次， 创建一个tmp的数组，

第一步：让nums后三个数，拷贝到tmp这个数组中去

第二步：再让前面的数，拷贝到tmp这个数组中去，

这样就实现了，nums这个数组向右旋转3次

时间复杂度：O(N) 空间复杂度： O(N)

思路三：****（最优解）

这种算法，时间复杂度O(N), 空间复杂度O(1)

下面我来重点介绍这种算法，

由图可知，数组的个数为n，旋转的次数为k

第一步：先n - k个逆置

第二步：后面k个逆置

第三步：整体逆置

结果便是旋转之后的数组

**注意：**当 n = k时候，

第一步就是先0个逆置，第一步就不旋转

第二步，后面k个逆置，相当于整体逆置

第三步，再整体逆置

结果就是没有旋转，

即 n = k时，不用旋转

基于这个，我们可以优化下计算

如果 k = n + 3,那么就相当于只旋转3次（因为n = k相当于不旋转）

下面是思路三的代码

void verse(int* nums, int left, int right) //先写一个逆置的函数
{
    while(left < right )
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    if(k >= numsSize)
    {
        k %= numsSize;
    }
    verse(nums, 0, numsSize - k- 1); //前n - k的逆置，不太清楚下标的，可以举个例子 
    verse (nums, numsSize - k, numsSize - 1 ); // 后 k 个逆置
    verse(nums, 0, numsSize - 1);            // 整体逆置
}

字符串旋转问题（补充）

题目：判断一个字符串，是否为另一个字符串旋转而来的 。

例如 abcded 向左旋转2个 为 cdedab

思路一：就是写一个字符串，然后再把它旋转的每种情况写出来，从而进行判断

这种方法肯定过于麻烦。

思路二**(优解)**：如果你对字符串函数比较了解，那么可以直接用字符串函数来做

首先，假设初始字符串数组str1, 有另一个字符串数组 str2， 判断str2是否有由str1 旋转而来的

第一步，使用strncat函数，将strncat(str1, str2, strlen(str2)); ----> 将字符串数组str2追加到str1上去。(不使用strcat函数， 原因是这个函数不能够追加自己本身，这样的话，就忽略了, str1与str2 相等的情况 即旋转的次数为 这个字符串数组大小的整数倍)

第二步，使用strstr函数， strstr(str1, str2);判断str2是否为str1的子集

最后，如果是子集 那么str2肯定就是由str1旋转得来的

当然，这个算法我们也可以有个优化，

如果str1与str2字符串长度不相等，那么么str2肯定就不是由str1旋转得来的。

代码如下：

温馨提示：，被追加的那个字符串数组大小，一定要大于等于两个字符串数组之和，不然会造成越界访问

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
int deduce(char* str1, char* str2)
{
    int first = strlen(str1);
    int second = strlen(str2);
    if (first != second)
    {
        return 0;
    }
    strncat(str1, str1, first);
    char* re = strstr(str1, str2);
    if (re == NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}   
int main()
{
     char arr1[30] = { "abcde" };
     char arr2[24] = { "deabc" };
    int ret = deduce(arr1, arr2);
    if (ret == 0)
    {
        printf("NO");
    }
    else
    {
        printf("YES");
    }
    return 0;
}

更新不易，麻烦多多点赞，欢迎你的提问，感谢你的转发，最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！