什么是算法？

一、什么是算法？

　定义：算法（Algorithm）

　　　　　 一个有限指令集

　　　　　 接受一些输入（有些情况下不需要输入）

　　　　　 产生输出

　　　　　 一定在有限步骤之后终止

　　　　　 每一条指令必须

　　　　　　 有充分明确的目标，不可以有歧义

　　　　　　 计算机能处理的范围之内

　　　　　　 描述应不依赖于任何一种计算机语言以及具体的实现手段

二、什么是好的算法？

两个关键点:

　　 空间复杂度 S ( n ) —— 根据算法写成的程序在执行时 占用存储单元的长度。这个长度往往与输入数据的 规模有关。空间复杂度过高的算法可能导致使用的 内存超限，造成程序非正常中断。

　　 时间复杂度 T( n ) —— 根据算法写成的程序在执行时 耗费时间的长度。这个长度往往也与输入数据的规 模有关。时间复杂度过高的低效算法可能导致我们 在有生之年都等不到运行结果。

 

+在分析一般算法的效率时，我们经常关注下面两种复杂度

 最坏情况复杂度 T_worst( n )

 平均复杂度 T_avg( n )

　　　　　　T_avg(n) <= T_worst(n)

-复杂度的渐进表示法：

　　 T(n) = O( f(n) ) 表示存在常数C >0, n₀>0 使得当 n >= n₀时

　　有T(n)<=C·f(n)

　　 T(n) = Ω( g(n) ) 表示存在常数 C >0, n ₀>0 使得当 n  n ₀ 时

　　有 T(n)>= C·g ( n )

　　 T( ) = Θ( h(n) ) 表示同时有 T(n) = O( h(n) ) 和 T( n) = Ω( h(n) )

如图所示：

+复杂度计算方法：

1.若两段算法分别有复杂度 T₁ (n) = O( f₁(n) ) 和 T₂ (n) = O( f₂ ( n) )，

则   T₁(n) + T₂(n) = max( O( f₁(n) ), O( f₂(n) ) )

　   　 T₁ (n)  T₂ ( n) = O( f₁(n)  f₂ ( n) )

2.若 T( n )是关于 n 的 k阶多项式，那么 T(n)= Θ ( n ^k ) 。

3.一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度。

4.if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大。

 

 

 

　                                                                                                      计算机小白的蜕变之路，艰辛亦单调，果断亦决绝。

 

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　                敬请批评指正！

 

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　                    　---yuhaow