程序 = 数据结构 + 算法
---某图灵奖得主
数据结构
基本数据单位
基本数据单位
数据>>数据对象>>>数据元素>>>>数据项
逻辑结构
常见的几种结构有集合结构、线性结构、树形结构、图形结构，其中：
线性结构：有序数据元素集合，比如队列、栈、字符串、数组、链表
树形结构：一对多，比如二叉树，红黑树
物理结构
顺序存储结构
链式存储结构
分两种，一种是顺序存储结构，一种是链式存储结构
算法
解决特定问题的指令序列
特点：输入输出、有穷性、确定性、可行性
评价标准：正确性、可读性、健壮性、效率高
效率度量
时间复杂度
大O表示法
- 用常数1取代运行时间中所有常数 3->1 O(1)
- 在修改运行次数函数中,只保留最高阶项
+2
+5 -> O(
- 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2
常见的时间复杂度
| 执⾏次数函数 | 阶 | 术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3 |
O( |
平方阶 |
| 5 |
O( |
对数阶 |
| 2n+3n |
O(n |
n |
| 6 |
O( |
⽴方阶 |
| 2n | O(2n) | 指数阶 |
时间复杂度描述的是算法的最坏情况。
空间复杂度(转载_罗小黑)
对于一个算法，所有的变量、指令、结果都需要存储空间，另外在算法的执行过程中，临时变量和临时结果也需要保留下来以便下一步计算，这些称为算法执行时的辅助空间。空间复杂度主要定性描述算法所需的辅助空间。
空间复杂度相对来说比较简单，只需要关注算法在执行时消耗的辅助空间即可，例如，
swap()函数中temp元素的消耗就是辅助空间。当然这个函数还能更高级，看大佬这里。
一个好的算法是什么样的？
正确性高、可读性强、健壮性高、效率高
正确性：毋庸置疑，首先必须正确，切实解决问题；
可读性：代码规范，易读注释，逻辑清晰，简单明了，但不是代码越少越好；
健壮性：输入考虑容错、边界值、输出；
效率：时间、空间按业务取舍；
欢迎留言讨论
网友评论