2、算法一些概念

本文总览

1、什么是算法

程序=数据结构 + 算法
数据结构：如何把现实世界的问题信息化，将信息存进计算机。同时还要实现对数据机构的基础操作。
算法：如何处理这些信息，以及解决实际问题。

2、算法的特性

• 有穷性。一个算法必须在执行有穷步之后结束，且每一步都可以在有穷时间内完成。算法必须是有穷的，程序可以是无穷的。
• 确定性。算法中每条指令必须又确切的含义，对于相同的输入只能得出相同的输出。
• 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入。一个算法可以有零个或多个输入，这些输入取自于某个特定的对象的集合。
• 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

3、算法的特质

• 正确性。算法应能够正确的解决求解问题。
• 可读性。算法应具有良好的可读性，以帮助人们理解。
• 健壮性。输入非法数据时，算法能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。
• 高效率（时间复杂度）与低存储量（空间复杂度）需求。

4、时间复杂度与空间复杂度

时间复杂度不能简单的统计程序运行的时间：

• 和机器性能有关，性能越高越快
• 和编程语言有关，语言越高级越慢
• 编译程序产生的机器指令指令有关
• 有些算法是不能事后再统计的
  算法时间复杂度：时间开销T(n)与问题规模n的关系
  
  
  一个算法的表达式，我们只需要保留阶层最高的项就可以了。
  因为算法的性能问题只有在n很大时才会暴露出来。
  加法规则：多项相加，只保留最高阶的项，且系数变为1。
  乘法规则：多项相乘，都保留
  顺口溜：常对幂指阶
  

最坏时间复杂度：最坏情况下算法的时间复杂度
平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间。
最好时间复杂度：最好情况下算法的事件复杂度

空间复杂度

考虑变量占用空间
递归占用空间