时间（空间）复杂度（结构篇）

复杂度是计算机科学中的一个基础概念，它帮助我们理解和评估算法的效率，对于算法设计和优化至关重要。算法的复杂度通常分为时间复杂度和空间复杂度两个方面。

前言：

众所周知：程序 = 算法  + 数据结构；衡量一个算法的标准就是算法效率。那么，算法效率是指算法执行的时间和所需的存储空间。在计算机科学中，算法效率通常通过时间复杂度和空间复杂度来衡量。

一、时间复杂度

1.1 时间复杂度的定义

• 时间复杂度是衡量算法执行时间随输入规模增长而变化的度量，它指示了算法的效率和性能。
• 时间复杂度通常使用大O符号（O）来表示，表示算法执行时间的上界。
• 时间复杂度描述的是算法执行时间与输入规模的增长趋势，而不是具体的执行时间。

1.2 时间复杂度的分析

表示方法：

大O 的表示法：是用于描述函数渐进行为的数学符号。

算法中的基本操作的执行次数，为算法 的时间复杂度。随着问题规模 n 的伴随某个函数f（n）变话记作：  

• 一般的忽略常数项。
• 只保留最高次幂项。

注意：我们通常表示的是一个数量级，而不是具体值或某个函数。

1.3 常见的时间复杂度

• 常数时间复杂度：O(1)，表示算法的执行时间不随输入规模的增长而变化，是最理想的情况。
• 对数时间复杂度：O(log n)，通常出现在二分查找等分治算法中。
• 线性时间复杂度：O(n)，表示算法的执行时间与输入规模成正比。
• 线性对数时间复杂度：O(n log n)，通常出现在快速排序、归并排序等分治算法中。
• 平方时间复杂度：O(n^2)，通常出现在嵌套循环的算法中。
• 指数时间复杂度：O(2^n)，通常出现在递归算法中。

• 多项式时间复杂度：O(n^k)，k可能是大于 2 的正整数，这意味着算法在大规模数据上的性能下降较快。

1.4 时间复杂度的计算以及简单的分析

通过分析算法中基本操作的执行次数，并根据输入规模的增长情况确定时间复杂度。

三种情况：

• 最好时间复杂度
• 平均时间复杂度
• 最坏时间复杂度

冒泡排序

// 计算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;
     }
}

分析：冒泡排序的时间复杂度：O（N^2）

解释：有N个个数，每次移动N-1次，剩下（N-1）移动（N-2）次，总共执行（N*（N-1）/2）次，根据大O表示就是：

折半查找（二分查找）

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
    assert(a);
 
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }
 
    return -1;
}

分析：折半查找的时间复杂度：最好是O( 1 ) ,最坏是O( log N ) ,该式表示：以2为底N的对数（仅限在计算机中表示）

解释：在查找的时候每次折半，也就是除以 2，一次是2^1，两次是 2^2，推广到N次数。

斐波那契数列（递归）

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

分析：斐波那契数列时间复杂度：O（2^n）

解释：

二、空间复杂度

2.1 空间复杂度的定义

• 空间复杂度（Space Complexity）是衡量算法在执行过程中临时占用存储空间大小的量度。
• 它反映了算法所需存储空间与输入数据大小之间的关系。
• 空间复杂度通常用大O表示法来表示。

2.2 空间复杂度的分析

同时间复杂度一样用大O表示法表示；也是表示一个数量级。记作：

2.3 常见的空间复杂度

• 常数阶：如果算法的空间复杂度不随问题规模 n 的变化而变化，即算法所需的存储空间是一个常数，那么空间复杂度为 O(1)。
• 线性阶：如果算法所需的存储空间与问题规模 n 成正比，即算法所需的存储空间随着 n 的增加而线性增加，那么空间复杂度为 O(n)。
• 多项式阶：如果算法所需的存储空间与问题规模 n 的关系可以表示为多项式函数，即空间复杂度为 O(n^k)，其中 k 是一个正整数。

• 对数阶：如果算法所需的存储空间与问题规模 n 的关系可以表示为对数函数，即空间复杂度为 O(log n)。
• 指数阶：如果算法所需的存储空间与问题规模 n 的关系可以表示为指数函数，即空间复杂度为 O(2^n)。

2.4 空间复杂度的计算以及简单分析

计算空间复杂度时，需要考虑算法在运行过程中显式申请的额外空间，而不是函数运行时所需要的栈空间，后者在编译期间已经确定好了

冒泡排序

// 计算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;
     }
}

分析：冒泡排序空间复杂度：O（1）

解释：仅仅使用了一个额外变量。

斐波那契数列（迭代）

// 计算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;
}

分析：斐波那契数列空间复杂度：O( N )

解释：开辟了N个空间。