【数据结构入门精讲 | 第二篇】一文讲清算法复杂度

上篇文章中我们引入了算法、数据结构、数据类型等概念，而要想衡量一个算法与数据结构是否为优质的，就需要一个衡量标准，这个衡量标准也是在我们实现一个好的算法时要遵循的原则。

基本概念

算法复杂度是衡量算法效率的指标，它描述了算法运行时间或空间需求随着输入规模增加而增加的趋势。通常分为时间复杂度和空间复杂度两种。

时间复杂度描述了算法解决问题所需的计算时间与输入规模之间的关系。常用的时间复杂度包括常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n^2)等，其中O表示“大O记号”。

空间复杂度描述了算法解决问题所需的内存空间与输入规模之间的关系。类似地，常用的空间复杂度也可以用大O记号表示。

由于空间复杂度较为简单，本文主要介绍时间复杂度。

渐进性态

算法复杂度的渐进性态是指随着问题规模的增大，算法的执行时间或者空间占用的增长趋势。通常情况下，我们关注的是算法在最坏情况下的表现，因为这可以给我们一个最保守的估计。

渐进性态数学表征

上界（Upper bound）：使用大 O 符号（O）表示算法的上界，描述了算法执行时间或空间占用随输入规模增长的最大限制。它给出了算法在最坏情况下的表现。

下界（Lower bound）：使用大 Ω 符号（Ω）表示算法的下界，描述了算法执行时间或空间占用随输入规模增长的最小限制。它给出了算法在最好情况下的表现。下界表示算法至少需要这么多的资源来解决问题。

平均情况（Average case）：使用大 Θ 符号（Θ）表示算法的平均情况，描述了算法在所有可能输入情况下的平均表现。它给出了算法的期望性能。

通常情况下，我们更关注算法的上界和平均情况，因为它们提供了对算法性能的更全面评估。下界通常用于证明某个算法的最佳性能限制。

复杂度排序：Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n^2)＜Ο(n^3)＜Ο(2^n)

算法复杂度的运算

我们通常以执行次数来匹配时间复杂度，看如下代码：

for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (sorted_arr[j] > sorted_arr[j + 1]) {
                int temp = sorted_arr[j];
                sorted_arr[j] = sorted_arr[j + 1];
                sorted_arr[j + 1] = temp;
            }
        }
    }

算法中使用了两个嵌套的 for 循环，执行了 n^2 次循环操作，因此，我们可以说这个算法的时间复杂度是 O(n^2)

一般来说，在运算时，遵循以下规则：

（1）可以忽略加法常数

O(3n + 131) 相当于 O(3n)

（2）与最高次项相乘的常数可忽略

O(88n^3) 相当于 O(n^3)

（3） 最高次项的指数大的，函数随着 n 的增长，结果也会变得增长得更快

所以O(n^8) > O(n^4)

（4）判断一个算法的（时间）效率时，函数中常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

例如：将O(3n^3+3n+1)的常数与次要项忽略，得到O(n^3)

顺序搜索算法

顺序搜索算法（Sequential Search Algorithm），也称为线性搜索算法，是一种简单直观的搜索方法。它逐个地检查待搜索的元素，直到找到目标元素或遍历完整个数据集。

示例如下：

#include <stdio.h>
int sequential_search(int arr[], int n, int target) {
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 返回目标元素的索引
        }
    }
    return -1;  // 目标元素未找到
}
int main() {
    int arr[] = {2, 5, 8, 10, 13, 6};
    int n = sizeof(arr) / sizeof(int);
    int target = 10;
    int result = sequential_search(arr, n, target);
    if (result != -1) 
    {
        printf("目标元素 %d 在数组中的索引为 %d\n", target, result);
    } 
    else 
    {
        printf("目标元素 %d 未找到\n", target);
    }
}

最好的情况即为：第一个元素就是要找的元素，常数时间O(1)，最坏的情况即为：元素不在数组中，执行n次，线性时间O(n)。得到平均时间复杂度为最好情况与最坏情况对应的复杂度之和的一半。即o((1+n)/2)，省略常数得到o(n)

二分搜索算法

二分搜索算法（Binary Search Algorithm），也称为折半搜索算法，是一种高效的搜索方法，它利用了已经排好序的数组的特点。它首先将待搜索区域缩小为一半，然后检查中间元素，如果目标元素等于中间元素，则找到目标；如果目标元素小于中间元素，则在左半部分继续搜索；如果目标元素大于中间元素，则在右半部分继续搜索。通过反复缩小搜索区域，最终可以找到目标元素或确定其不存在于数组中。

示例如下：

#include <stdio.h>
int binary_search(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;  // 返回目标元素的索引
        } else if (arr[mid] < target) {
            left = mid + 1;  // 在右半部分继续搜索
        } else {
            right = mid - 1;  // 在左半部分继续搜索}
    }return -1;  // 目标元素未找到}

int main() {
    int arr[] = {2, 5, 6, 8, 10, 13};
    int n = sizeof(arr) / sizeof(int);
    int target = 8;int result = binary_search(arr, n, target);
    if (result != -1) 
    {
        printf("目标元素 %d 在数组中的索引为 %d\n", target, result);
    } 
    else 
    {
        printf("目标元素 %d 未找到\n", target);
    }
    return 0;
}

其原理是每次将搜索区间减半，因此需要进行logn次比较，所以时间复杂度是O(logn)。