(数据结构初阶)时间复杂度与空间复杂度_时间复杂度是取最大的吗

一 时间复杂度

1.算法中的基本操作的执行次数，为算法的时间复杂度。时间是累计的。使用大O的渐进表示法 :估算。

2.在实际中一般情况关注的是算法的最坏运行情况，所以时间复杂度为取最大的。

3.基本操作递归了N次，时间复杂度为O(N)。

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

4.现基本操作递归了2^N次，时间复杂度为O(2^N)。

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

二 空间复杂度

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

2.递归的空间复杂度：

long long Factorial(size_t N)
{
  return N < 2 ? N : Factorial(N-1)*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 ;
}