算法与数据结构学习(一)数据结构基础
1. 数据结构
1.1 什么是数据结构
数据结构是 具有一定关系的同一类数据元素的集合。
书籍结构研究 数据的逻辑结果、数据的物理结构、数据之间的关系。
1.2 学习数据结构的必要性
了解数据结构,可以帮助我们理解数据在计算机中的存储形式。
合理的使用数据结构,能提高程序的运行效率。
2. 算法
没有明确定义,每个人对算法的理解有不同,在我看来算法就是解决问题的一些步骤。
2.1 怎么衡量算法的好坏
时间复杂度用来度量 算法执行的时间
空间复杂度用来度量 算法在执行时内存空间的占用
随着技术的不断提升,一般牺牲空间来换取时间。
2.1.1 时间复杂度
事前估算法
事后统计法
一般的,事前估算法比较靠谱,因为事后统计法在不同的硬件基础或者环境下,统计的结果可能不同。
算法语句的执行次数?
一般我们计算最坏时间复杂度
了解下得了…
2.1.2 空间复杂度
度量算法执行时候占用的空间的大小。
2.2 时间复杂度的计算
例:for循环
根据时间频度估算时间复杂度
循环n次数,时间频度为 T(n)=n,时间复杂度O(n)=
遵循原则:1.忽略常量项;2.忽略低次项;3.忽略系数;
常数阶O(1) 无循环
对数阶O(log(2n))
线性阶O(n)
线性对数阶O(n(log(2n)))
平方阶O(n^2)
…
2.3 常见的时间复杂度