数据结构与算法基础知识

前言：数据结构与算法是自己一直在逃避的一个方向，不想去面对它。以前自己也买过一系列的学习资料，可是由于自己的懒惰没能坚持学习下去，导致最近在面试的时候成了自己的软肋，每面试一次都会刺痛自己一次，所以自己决定好好补习一下。

当谈论计算机科学和编程时，数据结构和算法是两个基本概念。数据结构是为算法服务的，算法要作用在特定的数据结构之上。它们共同构成了解决问题和处理数据的核心，所以学习也从这里开始。

一、数据结构是什么？

简单理解
- 数据结构就是指一组数据的存储结构。
扩展理解：
- 它是计算机中用于存储、组织和管理数据的方式和技术。
- 数据结构可以看作是将数据按照特定的方式进行组织，以便于操作、检索和修改数据。
- 常见的数据结构包括数组、链表、栈、队列、树、图、散列表（哈希表）等。
- 不同的数据结构适用于不同类型的问题和操作，选择合适的数据结构可以影响程序的性能和效率。
类比现实世界：
- 可以把数据结构看作是数据的容器，就像箱子、抽屉一样，用来存放和组织数据。

二、算法是什么？

简单理解
- 算法就是操作数据的一组方法。
扩展理解
- 算法是一系列解决特定问题的步骤或操作序列。
- 它是一种用于执行特定任务的计算过程。
- 算法描述了一种从输入到输出的映射，它告诉计算机如何以一种有序的方式执行操作，以解决问题或达到预期的结果。算法可以用自然语言、伪代码或编程语言来描述。常见的算法包括排序算法、搜索算法、图算法、字符串匹配算法等。设计好的算法可以在最短的时间内得到正确的答案，并且在处理大量数据时能够高效运行。
类比现实世界：
- 算法就像是执行特定任务的步骤，就像做饭的步骤、组装家具的步骤等。

三、复杂度分析

1.复杂度分析方法是什么？
- 数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。
- 复杂度分析是计算机科学中的一个重要概念，用于评估算法在不同输入情况下所需的计算资源（如时间和空间）的增长情况。它帮助我们理解算法的效率以及在处理不同规模的问题时算法的表现。
2.时间复杂度和空间复杂度分别是什么？

时间复杂度：

时间复杂度描述了算法的运行时间随着输入规模的增长而增长的情况。通常使用大 O（"O" 表示 Order，顺序的意思）表示法来表示时间复杂度。大 O 表示法提供了一个关于算法运行时间增长的上界，即最坏情况下的运行时间。

例如，O(n) 表示线性时间复杂度，O(n^2) 表示平方时间复杂度。
- O(n) ：线性时间复杂度。
  - 当算法的运行时间与输入规模成线性关系时，可以用 O(n) 表示。这意味着算法的执行时间随着输入规模的增加而线性增加。
  - 例如，遍历一个数组、对每个元素执行一次操作等，都可以称为具有线性时间复杂度的算法。
- O(n^2) ：平方时间复杂度。
  - 当算法的运行时间与输入规模的平方成关系时，可以用 O(n^2) 表示。这意味着算法的执行时间随着输入规模的增加而呈平方增加,同时也意味着算法的效率会随着输入规模的增加而急剧下降，因为运行时间会迅速变得非常长。
  - 例如，嵌套循环中的每一轮循环都需要遍历输入数据，会导致总运行时间随着输入规模的平方增长。
  - 例如，如果有一个具有 O(n^2) 时间复杂度的算法，在输入规模从 10 增加到 100 时，算法的运行时间会从原来的 100 倍增加到 10000 倍。这种情况下，算法的性能会在处理大规模输入时变得相当糟糕。

这些表示法中的 "O" 代表了 "Order of"（顺序），而括号内的表达式则表示算法的增长率。在实际应用中，我们通常希望选择具有较低时间复杂度的算法，因为它们在处理大规模数据时更加高效。所以，O(n) 比 O(n^2) 更优，意味着在大多数情况下，具有线性时间复杂度的算法将比具有平方时间复杂度的算法更快。

注释：O(n^2) 中各个字符代表的含义

"O" 表示 Order（顺序）

"n" 则代表输入规模的大小。

指数 "2" 表示与输入规模的平方成正比。

空间复杂度：

空间复杂度描述了算法在执行过程中所需的额外内存空间随着输入规模的增长而增长的情况。和时间复杂度类似，空间复杂度也可以用大 O 表示法来表示。

3.复杂度分析的主要目标是：

确定一个算法在不同情况下的性能表现，从而在不同算法之间进行选择。
预测算法在处理大规模输入时的效率，避免在实际应用中出现性能问题。
帮助开发者理解和改进算法，以优化性能。

通常情况下，我们希望选择具有较低时间和空间复杂度的算法，因为它们在大规模数据处理时更加高效。然而，复杂度分析并不仅仅关注绝对的执行时间或内存使用量，它更着重于算法的增长率和趋势。在算法设计和评估中，复杂度分析是非常重要的工具。

四、时间复杂度的表示方法以及含义

常见的复杂度表示方法：

O(1) ：常数时间复杂度。表示算法的执行时间与输入规模无关，无论输入规模大小如何，执行时间都保持不变。例如，访问数组中的一个元素、执行固定次数的操作等。
O(log n) ：对数时间复杂度。表示算法的执行时间随着输入规模的增加而以对数速率增长。通常在使用二分查找等分治算法时出现。
O(n) ：线性时间复杂度。表示算法的执行时间与输入规模成线性关系。例如，遍历数组、对每个元素执行一次操作等。
O(n log n) ：线性对数时间复杂度。表示算法的执行时间随着输入规模的增加以 n log n 的速率增长。通常在一些高效排序算法如快速排序、归并排序等中出现。
O(n^k) ：多项式时间复杂度。表示算法的执行时间与输入规模的 k 次幂成正比。其中 k 是一个常数。
O(2^n) ：指数时间复杂度。表示算法的执行时间随着输入规模增加以指数速率增长。这种复杂度通常出现在解决组合问题时。
O(n!) ：阶乘时间复杂度。表示算法的执行时间随着输入规模增加以阶乘速率增长。这种复杂度通常出现在解决排列组合问题时。
O(sqrt(n)) ：平方根时间复杂度。表示算法的执行时间随着输入规模的平方根成正比。
O(n^(3/2)) ：立方根时间复杂度。表示算法的执行时间随着输入规模的立方根成正比。
O(log log n) ：双对数时间复杂度。表示算法的执行时间随着输入规模的对数的对数成正比。
O(n log log n) ：线性对数对数时间复杂度。表示算法的执行时间随着输入规模的 n 乘以对数的对数成正比。

上述表达式中各个字母的含义

O：这个大写字母 "O" 代表 "Order of"（顺序），表示时间复杂度的增长率。
n：通常代表输入规模的大小。在时间复杂度中，"n" 表示算法要处理的输入的数量。例如，数组中的元素个数、待排序的数据量等。
log n：这是对数函数，通常是以 2 为底的对数。在时间复杂度中，"log n" 表示算法运行时间与输入规模的对数关系。例如，二分查找等分治算法中通常会出现对数时间复杂度。
k：一个常数，表示多项式时间复杂度中的幂次。例如，O(n^2) 中的 "2" 就是一个常数。
! ：阶乘符号，用于表示阶乘时间复杂度。在时间复杂度中，O(n!) 表示算法运行时间与输入规模的阶乘关系。通常在排列组合问题中会出现。
sqrt(n) ：平方根函数，表示算法运行时间与输入规模的平方根成正比。在时间复杂度中，"sqrt(n)" 表示算法的执行时间随着输入规模的平方根成正比。这种情况通常出现在一些算法中，当算法的执行步骤数与输入规模的平方根成比例时。
n^(3/2) ：立方根函数，表示算法的执行时间与输入规模的立方根成正比。在时间复杂度中，"n^(3/2)" 表示算法的执行时间随着输入规模的立方根成正比。这种情况可能在一些特定的算法中出现。
log log n：双对数函数，表示算法的执行时间随着输入规模的对数的对数成正比。在时间复杂度中，"log log n" 表示算法的执行时间随着输入规模的对数的对数成正比。这种情况通常出现在一些特殊的问题和算法中。
n log log n：线性对数对数函数，表示算法的执行时间随着输入规模的 n 乘以对数的对数成正比。在时间复杂度中，"n log log n" 表示算法的执行时间随着输入规模的 n 乘以对数的对数成正比。这种情况可能在某些算法中出现。