前言：数据结构与算法是自己一直在逃避的一个方向，不想去面对它。曾经自己也买过一系列的学习资料，但是由于自己的懒惰没能坚持学习下去，导致最近在面试的时候成了自己的软肋，每面试一次都会刺痛自己一次，所以自己决议好好补习一下。
当谈论核算机科学和编程时，数据结构和算法是两个基本概念。数据结构是为算法服务的，算法要作用在特定的数据结构之上。它们共同构成了处理问题和处理数据的核心，所以学习也从这儿开始。
一、数据结构是什么？
-
简略了解
-
数据结构就是指一组数据的存储结构。
-
-
扩展了解：
- 它是核算机中用于存储、安排和管理数据的办法和技能。
- 数据结构能够看作是将数据依照特定的办法进行安排，以便于操作、检索和修改数据。
- 常见的数据结构包含数组、链表、栈、行列、树、图、散列表（哈希表）等。
- 不同的数据结构适用于不同类型的问题和操作，挑选合适的数据结构能够影响程序的功能和功率。
-
类比现实国际：
- 能够把数据结构看作是数据的容器，就像箱子、抽屉相同，用来存放和安排数据。
二、算法是什么？
-
简略了解
-
算法就是操作数据的一组办法。
-
-
扩展了解
- 算法是一系列处理特定问题的过程或操作序列。
- 它是一种用于履行特定使命的核算过程。
- 算法描绘了一种从输入到输出的映射，它告诉核算机怎么故一种有序的办法履行操作，以处理问题或到达预期的结果。算法能够用自然语言、伪代码或编程语言来描绘。常见的算法包含排序算法、搜索算法、图算法、字符串匹配算法等。设计好的算法能够在最短的时刻内得到正确的答案，并且在处理很多数据时能够高效运转。
-
类比现实国际：
- 算法就像是履行特定使命的过程，就像煮饭的过程、拼装家具的过程等。
三、复杂度剖析
-
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(n) ：线性时刻复杂度。
这些表明法中的 “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 乘以对数的对数成正比。这种状况可能在某些算法中出现。
