数据结构和算法简介

数据结构：存储和组织数据的方式，决定了数据的存储方式和访问方式。
算法：解决问题的思维、步骤和方法。
程序 = 数据结构 + 算法

算法

算法的独立性

算法是独立存在的一种解决问题的方法和思想，对于算法而言，实现的语言并不重要，重要的是思想，算法可以有不同的语言描述实现版本

算法的特点

• 有输入：算法具有0个或者多个输入
• 有输出：算法至少有1个或者多个输出
• 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
• 确定性：算法中的每一步都有确定的含义，不会出现二义性
• 可行性：算法的每一步都是可行的，即每一步都能够执行有限的次数完成

算法对比

对于同一个问题，我们给出了两种解决算法，在两种算法的实现中，我们对程序的执行时间进行了测算，发现两段程序执行的时间相差悬殊，由此我们可以得出结论：实现算法程序的执行时间可以反映出算法的效率
但是，单靠时间值衡量算法效率并不可靠

假设计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表花费多少时间单位，由此可以忽略机器环境的影响而客观的反应算法的时间效率

$$.代码执行总时间(T)=操作步骤数量\ast 操作步骤执行时间$$

时间复杂度

时间复杂度表示一个苏娜发随着问题规模不断变化的最主要趋势，通常用来衡量一个算法的优劣

时间复杂度的表示形式

大O 记法 为算法的时间复杂度随数据量变化的关系曲线，通常由最高次项决定，当数据量比较高时低次项的影响相对于高次项就很小，为了方便可以忽略

时间复杂度的计算规则

• 基本操作 时间复杂度为O(1)
• 顺序结构 时间复杂度按加法计算
• 循环结构 时间复杂度按乘法计算
• 分支结构 时间复杂度取最大值
• 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略
• 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

最优最坏时间复杂度

分析算法时，存在集中可能的考虑

• 算法完成工作最少需要多少基本操作，即 最优时间复杂度
• 算法完成工作最多需要多少基本操作，即 最坏时间复杂度
• 算法完成工作平均需要多少基本操作，即 平均时间复杂度

最优最坏时间复杂度的作用

• 最优时间复杂度：反映的知识最乐观最理想的情况，没有参考价值
• 最坏时间复杂度：算法的一种保证，表示算法在此种程度的基本操作中一定能完成工作
• 平均时间复杂度：是对苏娜发的一个全面评价，因此它完整全面的反映了这个算法的性质，但另一方面，这种平衡并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用苏娜发的实例分布可能并不均匀而难以计算。

我们主要关注算法的最坏情况，即最坏时间复杂度

常见的时间复杂度

• $O(1)$ 常数阶
• $O(logn)$ 对数阶
• $O(n)$ 线数阶
• $O(n^2)$ 平方阶
• $O(n^3)$ 立方阶

效率高到低分别是
$$O(1)>O(logn)>O(n)>O(n\ast logn)>O(n^2)>O(n^3)$$

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，类似于时间复杂度。一个算法的空间复杂度$S(n)$ 定义为该算法所耗费的存储空间