数据结构-复杂度计算经典案例（二）

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

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}
复制代码

// 计算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;
  }
}
复制代码

// 计算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;
}
复制代码

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

// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}
复制代码