数据结构算法和算法效率评价数据结构知识总结

一、算法的基本概念
算法（Algorithm）:是针对特定问题的问题求解步骤的一种描述。它是指令的有限序列；算法具有如下五个重要特征：
1.1、有穷性：有穷步骤，有穷计算时间；
1.2、确定性：每一条指令必须有确切的含义。换句话说就是：对于相同的输入必须得出相同的输出结果。
1.3、可行性：算法是可行的，算法中描述的操作都是可以通过已经实现的基本运算执行有限次得到。
1.4、输入
1.5、输出
一个好的算法有如下几个评价标准：
1.正确性
2.可读性
3.健壮性
4.效率与低存储量的要求
二、算法效率的度量
2.1时间复杂度：一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有的语句频度之和记作T（n）,他是该算法问题规模n的函数，时间复杂度主要分析T（n）的数量级；算法中的基本运算（循环中的最深循坏内语句）的频度与T（n）同数量级。所以通常用算法中基本运算的频度f（n）来分析算法的时间复杂度。因此时间的复杂度记作：
T(n) = O(f(n))
以上的O表示为T（n）的数量级。其严格的数学含义为：若T（ n）和f(n)是定义在正整数集合上的两个函数。则存在正整数C和 n0，使得n>=n0,都满足0<=T(n)<=C*f( n)
另外算法的时间复杂度不仅仅只是依赖以问题规模n,同时也取决于输入参数的性质(比如：数据的初始值)；例如以下例子：
在数组中A[0……N-1]，查找最大值K

i = 1; while(i>=0&&A[i] !=K) i--; return i;

在此算法，时间复杂度不仅与最内层循环（i–）的赋值次数有关，还有A数组中的各元素值和目标最大值K有关:
1.若A中没有与K相等的数，则算法中的（i–）的频度为f(n);
2.若A的最后一个元素的值与K相等。则（i–）的频数为f(n) = 0;
【数据结构算法和算法效率评价】以下是常见的几个复杂度概念：
最坏时间复杂度：在最坏情况下的时间复杂度；
平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度：在最好的情况下，算法的时间复杂度。
一般情况下总是先考虑最坏时间复杂度，以保证算法的时间复杂度不会超过这个最大值。
时间复杂度的两个基本规则：
1.加法法则：
T（n）=T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)));
2.乘法法则：
T(n) = T1(n)T2(n) = O(f(n)) O(g(n)) = O(f(n)*g(n))
3.常见的时间复杂度比较：
O（1）< O（log2n）< O（n） < O（nlog(2n)）< O(n^2)< O(n^3)< O(2^n)