数据结构与算法

发表于 2022-09-05 更新于 2022-09-06 分类于数据结构篇阅读次数：本文字数： 3.8k

什么是数据结构与算法

回顾我们之前的C语言程序设计阶段，我们已经接触过基本数据类型，并且能够使用结构体对数据进行组织，我们可以很轻松地使用一个结构体来存放一个学生的完整数据，在数据结构学习阶段，我们还会进一步地研究。

数据结构

那么,我们来看看,什么是数据结构呢?
什么是数据结构与算法

数据结构(datastucture)是带有结构特性的数据元索的集合，它研究的是数据的逻组结松和数据的物理结构以及它们之间的相互关系。

比如现在我们需要保存100个学生的数据，那么你首先想到的肯定是使用数组吧!没错，没有什么比数组更适合存放这100个学生的数据了，但是如果我们现在有了新的需求呢?我们不仅仅是存放这些数据，我们还希望能够将这些数据按顺序存放，支持在某个位置插入一条数据、删除一条数据、修改一条数据等，这时候，数组就显得有些乏力了。

我们需要一种更好的数据表示和组织方式，才能做到类似于增删改查这样的操作，而完成这些操作所用到的方法，我们称其为“算法”，所以数据结构和算法，—般是故在一起进行讲解的。

算法

比如现在我们希望你求出1-100所有数字的和,请通过程序来实现:

int main {
int sum = d;
for (int i - i; i <- 100; ++i)
sum +- i;
printf("%d" ，sum);
}

我们很容易就能编写出这样的程序，实际上只需要一个for循环就能搞定了，而这就是我们设计的算法。

/Users/nagocoler/Dev.localized/untitled/cmake-build-debug/untitled
5050

延程己结束,返出代码0

在之前的C语言程序设计阶段，我们其实已经学习了许多算法，包括排序算法、动态规划等。

当然，解决问题的算法并不是只有一种，实际上我们上面的方式并不是最优的算法，如果想要求得某一段整数的和，其实使用高斯求和公式能够瞬间得到结果:

1	(首项 + 末项) * 项数 / 2

所以，我们完全没必要循环那么多次进行累加计算,而是直接使用数学公式:

1
2
3

int mainC { 
    printf(""%d"，1 + 100 * 100 / 22;
 }

可见，不同的算法，执行的效率也是有很大差别的，这里我们就要提到算法的复杂度了。衡量一个算法的复杂程度需要用到以下个标:

·时间复杂度T(n)∶算法程序在执行时消耗的时间长度，一般与输入数据的规模n有关。

·空间复杂度5(n):算法程序在执行时占用的存储单元长度，同样与数据的输入规模n有关，大部分情况下，我们都是采取空间换时间的夏法。

比如我们上面的两种算法，第一种需要执行n次循环，每轮循环进行一次累加操作，而第二种只需要进行一次计算即可。实际中我们计算时间复杂度时，其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用О渐进表示法。

·大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

而这里的循环次数，实际上就是我们需要知道的大致执行次数，所以第一种算法的时间复杂度为:O(n)，其中n就是项数，因为它一执行n次计算才能得到最后的结果。而第二种算法的时间复杂度为:0(1)，因为它只需要执行一次计算（更准确的说它的执行次数是一个常数，跟项数n毫无关系），显然，当n变得非常大时，第二种方法的计算速度远超第一种。

再比如我们之前使用的冒泡排序算法，需要进行两轮循环，而循环的次数在经过优化之后为(n - 1)(n - 1)/2”，得到的结果中包含了一个n的平方，此时这种算法的时间复杂度就来到O(n^2)了。

在不同的空间复杂度下，可能n小的时候还没什么感觉，但是当n变得非常大时，差距就不是一点半点了，我们来看看常用函数的增长曲线:

所以我们在设计算法的时候，一定要考虑到时间和空间复杂度的问题，这里列出常用函数的增长表：

函数	类型	解释
O(1)	常数阶	如果算法能够优化到这个程度，那么基本上算是最快的算法了。
O(log(n)/log(2))	对数阶	仅次于常数阶的速度，我们后面会介绍的二分搜索算法，就能够到达这个级别。
O(n)	线性阶	线性表插入、删除数据，包括动态规划类算法能够达到线性阶。
O(nlog^2n)	线性对数阶	相当于在对数阶算法外层套了一层线性阶循环。
O(n²)	平方阶	我们前面学习的冒泡排序，需要进行两轮循环，实际上就是平方阶。
O(n³)	立方阶	从立方阶开始,时间复杂度就开始变得有点大了。
O(2^n)	指数阶	我们前面学习的冒泡排序，需要进行两轮循环，实际上就是平方阶。
O(n!)	阶乘	这个增长速度比指数阶还恐怖，但是一般很少有算法能达到这个等级。

我们在编写算法时，一定要注意算法的时间复杂度，当时间复杂度太大时，可能计算机就很难在短时间内计算出结果了。

算法例题：二分搜索算法

现在有一个从小到大排序的数组，给你一个目标值target，现在请你找到这个值在数组中的对应下标，如果没有，请返回-1：

int search(int* nums, int numsSize, int target){
    //请实现查找算法
}

int main() {
    int arr[] = {1, 3, 4, 6, 7,8, 10, 11, 13, 15}, target = 3;
    printf("%d", search(arr, 10, target));
}

此时，最简单的方法就是将数组中的元素一个一个进行遍历，总有一个是，如果遍历完后一个都没有，那么就结束：

int search(int* nums, int numsSize, int target){
    for (int i = 0; i < len; ++i) {
        if(nums[i] == target) return i;   //循环n次，直到找到为止
    }
    return -1;
}

虽然这样的算法简单粗暴，但是并不是最好的，我们需要遍历n次才能得到结果，时间复杂度为O(n)，我们可以尝试将其优化到更低的时间复杂度。这里我们利用它有序的特性，实际上当我们查找到大于目标target的数时，就没必要继续寻找了：

int search(int* nums, int numsSize, int target){
    for (int i = 0; i < len; ++i) {
        if(nums[i] == target) return i;
        if(nums[i] > target) break;
    }
    return -1;
}

这样循环进行的次数也许就会减小了，但是如果我们要寻找的目标target刚好是最后几个元素呢？这时时间复杂度又来到到了O(n)，那么有没有更好的办法呢？我们依然可以继续利用数组有序的特性，既然是有序的，那么我们不妨随机在数组中找一个数，如果这个数大于目标，那么就不再考虑右边的部分，如果小于目标，那么就考虑左边的部分，然后继续在另一部分中再次随机找一个数，这样每次都能将范围缩小，直到找到为止（其思想就比较类似于牛顿迭代法，再次强调数学的重要性）

而二分思想就是将一个有序数组不断进行平分，直到找到为止，这样我们每次寻找的范围会不断除以2，所以查找的时间复杂度就降到了)

O(log2^n)

相比一个一个比较，效率就高了不少：

那么现在我们就可以利用这种思想，编写出二分搜索算法了，因为每一轮都在进行同样的搜索操作，只是范围不一样，所以这里直接采用递归分治算法：

int binarySearch(int * nums, int target, int left, int right){  //left代表左边界，right代表右边界
    if(left > right) return -1;   //如果左边大于右边，那么肯定就找完了，所以直接返回
    int mid = (left + right) / 2;   //这里计算出中间位置
    if(nums[mid] == target) return mid;   //直接比较，如果相等就返回下标
    if(nums[mid] > target)    //这里就是大于或小于的情况了，这里mid+1和mid-1很多人不理解，实际上就是在下一次寻找中不算上当前的mid，因为这里已经比较过了，所以说左边就-1，右边就+1
        return binarySearch(nums, target, left, mid - 1);   //如果大于，那么说明肯定不在右边，直接去左边找
    else
        return binarySearch(nums, target, mid + 1, right);  //如果小于，那么说明肯定不在左边，直接去右边找
}

int search(int* nums, int numsSize, int target){
    return binarySearch(nums, target, 0, numsSize - 1);
}

参考b站大佬青空の霞光