数据结构与算法(基础)

数据结构是什么

数据结构（Data Structure）是计算机中存储、组织数据的方式。

常见的数据结构有堆栈（Stack）、队列（Queue）、数组（Array）、链表（Linked List）、数（Tree）、图（Graph）、堆（Heap）、散列表（Hash Table）等。

算法是什么

算法（Algorithm） 在数学和计算机科学中，指一个被定义好的、计算机可施行器指示的有限步骤或次序，常用语计算、数据处理和自动推理。算法是有效方法，包含一系列定义清晰的指令，并可于有限的时间及空间内清除的表述出来。

算法的特性

• 输入：一个算法必须有零个或以上输入量。
• 输出：一个算法应有一个或者以上输出量，输出量是算法计算的结果。
• 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确的符合要求或期望，通常要求实际执行结果是确定的。
• 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
• 有效性：又称可行性，能够实现算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

常用的设计模式

• 分治法
• 动态规划法
• 贪心算法
• 线性规划法

时间复杂度

影响执行时间，越复杂执行时间越长。

常见的时间复杂度有：常数阶O(1)、对数阶O(log n)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n2)、立方阶O(n3)、…、k次方阶O(nk)、指数阶O(2n)。随着问题规模nn的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

影响内存的消耗，越复杂内存消耗的越大。

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。