数据结构与算法-------算法入门

1.算法：解决问题的方法。

2.算法的描述：比方说自然语言，流程图，伪代码等等。

3.算法与程序：算法是一种方法，程序是利用某种程序设计语言来对算法进行表示。

4.算法的性质：有穷性，确定性，可行性，输入，输出

5.要求：正确性，可读性（是不是赏心悦目？），健壮性（如果我故意输入不符合初始条件的数据，会蹦出来非常奇怪的数字吗？），高效性。

立足点：

1.时间效率：所花费的时间

（1）事后统计

（2）事前统计

算法运行的时间=∑每条语句执行次数×该语句执行依次所需要的时间。

往往利用渐进时间复杂度来进行计算，也就说所有语句的次数的数量级。

方法：找出语句频度最大的那条语句作为基础语句，计算基础语句的频度得到问题规模n的某个函数f（n），取其数量级用符号O表示

2.空间效率：所占用的空间（通过计算程序中创建的变量，数组等所占用的内存）

3.关键点：在这个评估中，往往我们很难兼顾时间与空间，所以要根据客户的具体要求来进行取舍。

4.在具体的情境下，时间复杂度往往都与n的大小有关，因此，在评估时，我们总是按最坏的情况处理，即n总是最大。

5.对于复杂算法Tn，可以将其拆分为fn+Fn或者是fn×Fn，那O(Tn)=O(fn)+O(Fn)或者O(Tn)=O(fn)×O(Fn)。

1.for(i=0;i<n,i++) //n+1

{

arr1[i]=0;//n

for(j=0;j<n;j++)//n×(n+1)

arr2[j]=0;//n

}

则总执行n²+3n+1，那复杂度则为O（n²）

2.for（i=0；i<n;i++）

int tmp=arr[n-i-1];

arr[n-i-1]=arr[i];

arr[i]=arr[n-i-1];

因为这个过程中他只使用了tmp这个int型变量，因此空间复杂度为O(1)。

3.另外，必须要明白一件事，我上面举的例子是最简单的，事实上有许多数学公式需要熟记，列如级数求和等等。

四.小节