什么是算法
程序= 数据结构（用数据描述问题存到计算机）+算法（高效的处理数据）
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
算法的特性
- 有穷性，必须在有穷步之后结束，且每一步都可以在有穷时间内完成
算法是有穷的，程序是无穷的
- 确定性：相同的输入只能得到相同的输出
- 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
好的算法是什么样的：
- 正确性 能够正确求解问题
- 可读性 便于人类理解
- 健壮性 非法数据，算法要做出反应进行处理，而不会输出莫名奇妙的结果
- 高效率（时间复杂度低）与低储存量（空间复杂度低）的需求
时间复杂度
我们评估一个算法要评估他的执行效率这带来的以下的问题，难道我们要让算法运行 然后统计运行时间吗？
这时候我们需要引入一个时间复杂度的概念
时间复杂度是用来事前预估算法时间开销T(n)与问题规模n的关系
一个非常简单的例子：
查看每一步需要执行多少次 T(n)即为带问题规模n的一个函数来表示执行的次数
提示：
时间复杂度多用于评估问题规模较高的时间开销问题，所以我们引入一个O(n)的概念，只考虑含n表达式中阶数高的部分 因为他对整个程序的运行时间起到了决定性的作用。
大O表示同阶，同等数量级。n->♾️，两者之比为常数。
加法规则与乘法规则
需要背
所以O(n³)更大 最终结果就是O(n³)
数学推导：
速记方法：常对幂指阶
顺序执行的代码只影响常数项O（1） ，可以忽略
找循环中最内层的基本操作分析他执行次数与n的关系即可（根据加法原理 取最高阶）
算法性能问题只有n很大才会暴露出来
空间复杂度
这个部分用几个例子就可以清楚
第一个O(1)型 所需内容空间固定
第二个O(n)型
- 加法原则与乘法原则
- 函数递归调用
提示：
存储涉及原理内容：函数调用栈，可以参考该文章学习：
所以S(n)=4(kn+16)
重点：
S(n)=O(n)
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。