深入解析算法的时间复杂度与空间复杂度：衡量算法效率的关键指标

时间复杂度

时间复杂度衡量的是算法执行所需的时间随输入数据大小（通常表示为 n）的增长而增长的趋势。我们使用大O表示法（Big-O notation）来描述时间复杂度。

示例：

对于Fibonacci数列的递归实现，如您所示：

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

这个算法的时间复杂度是指数级的，因为它对每个子问题都进行了递归调用，导致了很多重复的计算。具体的时间复杂度是 O(2^n)，因为对于每个 Fib(N)，都会进行两次递归调用 Fib(N-1) 和 Fib(N-2)，每次递归调用都会导致问题规模减半，直到达到基本情况。

然而，对于您给出的双重循环的示例，时间复杂度是 O(N^2)，因为外层循环和内层循环都执行了 N 次。

大O的渐进表示法：

• O(1)：算法的运行时间不随输入数据的大小而改变。
• O(log n)：算法的运行时间以对数形式增长。
• O(n)：算法的运行时间与输入数据的大小成线性关系。
• O(n^2)：算法的运行时间与输入数据的大小的平方成比例。
• O(n!)，O(2^n) 等：表示算法的运行时间随着输入数据的大小增长得非常快，通常是不切实际的。

空间复杂度

空间复杂度衡量的是算法在执行过程中所使用的额外存储空间的大小。同样地，我们使用大O表示法来描述空间复杂度。

示例：

对于Fibonacci数列的迭代实现，如果不需要存储整个数列，空间复杂度是 O(1)，因为它只使用了有限的几个变量。

但是，对于您给出的Fibonacci数列的数组实现：

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

这个算法的空间复杂度是 O(n)，因为它使用了一个大小为 n+1 的数组来存储Fibonacci数列的每一项。

对于冒泡排序（BubbleSort）算法，由于它只使用了几个额外的变量（如交换标志和循环变量），所以其空间复杂度通常是 O(1)。但是，如果我们考虑递归实现，并且递归调用在函数栈上产生了额外的空间，那么空间复杂度可能会增加。

注意：

• 在讨论空间复杂度时，我们通常只考虑额外的存储空间，而不考虑用于存储输入数据的空间。
• 在计算空间复杂度时，我们还需要考虑递归调用在函数栈上产生的额外空间（如果算法是递归的）。
• 与时间复杂度不同，空间复杂度可能受到具体实现的影响，例如使用动态内存分配（如malloc）或使用静态数组。