数据结构与算法_数据结构和算法

一、什么是算法？

算法即是一些问题的解决方法和思想。
例1：计算1到10000的和是多少？

算法1: 循环10000次，累加1到10000到所有数字。

算法2: 利用等差数列的特性计算 (1 + 10000) * (10000 / 2)。

上面两种算法都是解决事例问题的方法，区别是计算量不同，显然算法2更高效。这说明：

1. 解决同一个问题不止一种算法；
2. 算法有优劣之分；

二、什么是数据结构？

数据结构是算法的基石，算法的实现是已数据结构为依托的。它是数据的组织、管理和存储方式，其作用是更高效地访问和修改数据。

常见数据结构：

1.线性结构

线性数据结构是最简单的数据结构，包括：数组、链表，以及他们的衍生结构：堆、栈、队列、哈希表等。

2.树

树是相对复杂的数据结构，最具代表性的是二叉树，衍生结构包括红黑树、二叉堆等。

3.图

图是更复杂的数据结构，数据中呈现多对多的关联关系。

4.其他数据结构

上面3种数据结构的应用范围依次递减，除此之外的数据结构患有还有：位图、跳表、哈希链表等。

三、算法有那些？

算法中最具代表性的是排序算法，包括：

1. 冒泡排序；
2. 插入排序；
3. 快速排序；
4. 鸡尾酒排序；
5. ...

其他算法包括：

1. 查找最大值、最小值；
2. 求两个数的最大公因数；
3. 贪婪算法；
4. 狄克斯特拉算法；
5. K最近邻算法；
6. ...

四、如何评估算法的优劣？

衡量算法优劣最重要的两个标准是算法的时间复杂度和空间复杂度，这两种复杂度都用大O表示法来表示（其中O表示一个常量系数）。

例1:给一个长度为n大数组中每个数字都自加1。

// 解：
const arr = [2, 3, 2, 5, 1]; // 假设长度为n
for (let i = 0; i < arr.length; i++) {
    arr[i]++;
}

注：
这种算法在时间复杂度上进行了arr的长度n次单元操作，所以时间消耗和长度n是线性的。在空间上，没有独立开辟新的存储空间，所以空间消耗与长度n无关，因此：

时间复杂度：$T(n) = O(n)$

空间复杂度：$S(n) = O(1)$

例2:对一个数组进行冒泡排序

var temp = null;
for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

注：

设该算法的数据量arr的长度为n，其时间损耗为: $n + (n - 1) + ... + 1 = 0.5n^{2} + 0.5n$，空间损耗与n无关。用大O表示法表示时，我们只取对应数学公式的最高次幂，并忽略系数，所以:

时间复杂度：$T(n) = O(n^{2})$

空间复杂度：$S(n) = O(1)$

下一篇为《常用排序算法》

tip:有用的话请在右侧点