数据结构和算法初步

算法与数据结构

1.什么是数据结构？

数据结构(data structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定 关系的数据元素的集合。

1.1 常见数据结构

2.什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用 系统的方法描述解决问题的策略机制。

一句话描述：算法是一种解决特定问题的思路

比如：LRU算法，近少使用，解决的就是当空间不够用时，应该淘汰谁的问题，这是一种策略，不 是唯一的答案，所以算法无对错，只有好和不好。

2.1常见算法

3.算法复杂度

3.1 时间复杂度

3.2 空间复杂度

空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系

比如将一个数组拷贝到另一个数组中，就是相当于空间扩大了一倍:T(n)=O(2n)，忽略系数。即为：

O(n)，这是一个非常常见的空间复杂度，比如跳跃表、hashmap的扩容 此外还有:O(1)，比如原地排序、O(n ) 此种占用空间过大

由于现在硬件相对比较便宜，所以在开发中常常会利用空间来换时间，比如缓存技术

典型的数据结构中空间换时间是：跳跃表

在实际开发中我们也更关注代码的时间复杂度，而用于执行效率的提升

4.常见算法

1、分治法；2、贪心算法，一种对某些求最优解问题的更简单、更迅速的设计技术；3、动态规划算法；4、回溯法，一种选优搜索法；5、分支限界法。