数据结构 | 算法的时间复杂度和空间复杂度【详解】(二)

数据结构 | 算法的时间复杂度和空间复杂度【详解】(一):https://developer.aliyun.com/article/1426583

实例7：

计算BinarySearch的时间复杂度？

• 这里一眼看就是一个二分查找~~
• 我们这里的是不是复杂度数O(N)?

int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;
  int end = n - 1;
  // [begin, end]：begin和end是左闭右闭区间，因此有=号
  while (begin <= end)
  {
    int mid = begin + ((end - begin) >> 1);
    if (a[mid] < x)
      begin = mid + 1;
    else if (a[mid] > x)
      end = mid - 1;
    else
      return mid;
  }
  return -1;
}

• 首先先说结论，这里是O(logN)，我们这里看代码是看不出来的，要看思想~~
• 首先二分查找的前提是有序
• 这个数组假设有n个值
  
• n/2/2/…/2 = 1（最坏的情况~~）
  
• 我们这里除了多少个2？找了多少次就除了多少个2
  
• 假设找了x次–>2^x = N --> x = logN
  

我们这里的这个以2为底的logN是不是很不好写…我们平时就可以不写了~~，直接写成O(logN)

但是有的书或者博客上面写成O(lgN)，我们不建议~~，和我们数学里面是有些混淆的

学了复杂度我们要指定O(logN)是一个很腻害的算法我们下面进行对照~~

• 这里对应的有暴力查找（数组过一遍查找）：O(N)
• 二分查找：O(logN)

比如：

• 如果我把中国所有人的信息放到一个数组中，我们要找多少次？

我们就只需要找31次，是不是很厉害~~

• 我们这里前提是要有序，有序是要有代价的，需要排序，如果有一个新生儿出生了，就要插入，如果有人离世了，就要删除了，这就很难~~
• 这里有更好的数据结构，有：AVL树，红黑树，哈希表，这些我们后面都会讲解~~

实例8：

计算阶乘递归Fac的时间复杂度？

• 首先来看这是一个阶乘，很多同学肯一看是O(1)，又不太敢确认
• 我们先说结论—>O(N)

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

• 阶乘是不是有多次函数的调用，每次调用是常数次O(N)，有N次调用就是O(N)~~

我们再来变一下形~~，我们来看下面，这个的时间复杂度是多少呢？

我们先说结果–>O(N^2)，然后我们进行分析~~

long long Fac(size_t N)
{
  if (0 == N)
    return 1;
  for (size_t i = 0; i < N; ++i)
  {
    //....
  }
  return Fac(N - 1) * N;
}

• 这里是咋算的？
• 每次递归走了一次循环，递归计算的是多次调用累加，多少次调用？N次调用，每次调用多少趟？这不是N，每次都在变化，当N为10时，循环走10次，当N是9时，循环走9次
• 递归次数累加是一个等差数列 （0~N）的等差数列

• 所以就是O(N^2)~~

实例9：

计算斐波那契递归Fib的时间复杂度？

• 斐波那契数列类似于细胞分裂，一个分裂成两个，两个分裂成4个…

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

• 这里仔细看，这是一个等比数列和~~

• 这里可以用到错位相减法，如图：

• 根据大O渐进表示法，时间复杂度也就是O(2^N)，这是一个成指数增长的~~

5.空间复杂度

• 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时额外占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
• 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
• 注意： 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

案例1：

计算BubbleSort的空间复杂度？

• 这里的这个空间复杂度是多少？—>>O(N)还是O(1)

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(N)

案例2：

计算Fibonacci的空间复杂度？

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

• 这里我们malloc了·n+1·个空间
• 其他的都忽略掉，所以就是O(N)

案例3：

计算阶乘递归Fac的空间复杂度？

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

• 这里递归空间复杂度计算，也是空间累加，但是不同的是空间可以重复利用
• 所以这里就是O(N)

6.复杂度的oj练习

6.1 消失的数字

OJ链接

• 这里题目要求在时间复杂度上O(n)我们介绍三种方法，看看哪种方法适合这道题~~

方法一：

1. 先冒泡排序
2. 遍历，当前值+1，不等于下一个数

这个时间复杂度是O(N^2)

方法二：

1. 将数组的每个元素异或0
2. 遍历，再将异或出来的结果每个再异或

这个时间复杂度是O(N)

方法三：

1. 0到n等差数列公式计算和((首项 + 尾项) * 项数)/2
2. 依次减掉数据中的值，剩下的就是消失的数字

这个时间复杂度是O(N)

• 可见只有方法二和方法三符合题目要求，下面我们就写一下这个代码

方法二的代码：

int missingNumber(int* nums, int numsSize){
    int N = numsSize;
    int sum = ((0+N)*(N+1))/2;
    for(int i= 0;i<numsSize;i++){
        sum-=nums[i];
    }
    return sum;
}

方法三的代码：

int missingNumber(int* nums, int numsSize){
    int x = 0;
    for(int i = 0;i<numsSize;i++){
        x^=nums[i];
    }
    for(int i = 0;i<=numsSize;i++){
        x^=i;
    }
    return x;
}

6.2 旋转数组

OJ链接

• 我们这个题肯有些同学在C语言的时候做过

我们先来看思路一：

• 思路一的时间复杂度是多少？

• 可能有的同学算出来的是O(N*K)，不完全正确~~

• 最好的情况：k % N = 0，k = 7，旋转0次！！！是O(1)。k是N的倍数时，不需要旋转~~
• 最坏的情况：k % N = N - 1时，比如13次旋转的最多，20次最多…
• 所以这个题的真正复杂度是O（N*(N-1)）—>O(N^2)

那么我们要求时间复杂度是O(N)，那么我们怎么优化呢？

我们这里就要看思路二：

• 这里很明显是O(N)

代码如下：

void reverse(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;
    }
    reverse(nums,0,numsSize-1);
    reverse(nums,0,k-1);
    reverse(nums,k,numsSize-1);
}

• 注意这里k一定要%numsSize，否则会报错~~

思路三：

空间换时间

• 这里的时间复杂是O(N)，空间复杂度是O(N)

代码如下：

void rotate(int* nums, int numsSize, int k) {
  k %= numsSize;
  int tmp[numsSize];
  int j = k;
  //拷贝前n-k个
  for (int i = 0; i < numsSize - k; i++) {
    tmp[j++] = nums[i];
  }
  //拷贝后k个
  j = 0;
  for (int i = numsSize - k; i < numsSize; i++) {
    tmp[j++] = nums[i];
  }
  //拷贝回原数组
  for (int i = 0; i < numsSize; i++) {
    nums[i] = tmp[i];
  }
}

好了，数据结构的算法的时间复杂度和空间复杂度到这里就结束了~~

如果有什么问题可以私信我或者评论里交流~~

感谢大家的收看，希望我的文章可以帮助到正在阅读的你🌹🌹🌹