ADT 即 Abstract data type,抽象数据类型的三个主体是数据对象 + 关系 + 操作。 我们可以用下面的格式描述抽象数据类型:
ADT 抽象数据类型名{ 数据对象:it is..... 数据关系:they are..... 基本操作: 操作1:done sth.... 初始条件:.... 操作结果:.... 操作2:done sth.... 初始条件:.... 操作结果:.... } ADT 抽象数据类型名
有穷性(时间有穷、步骤有穷)、确定性(没有歧义)、可行性、输入、输出
正确性(至少可以得到正确结果,对于非法输入也应有提示)、可读性、健壮性、高效性(时间 + 空间)
T(n) = O(f(n))
,它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同。S(n)=O(f(n))
,其中,n 为问题规模,f(n) 表示关于 n 所占存储空间的函数。//算法1
for(i = 0;i < n/2;i++){
t = a[i];
a[i] = a[n-i-1];
a[n-i-1] = t;
}
//算法2
for(i = 0;i < n;i++)
b[i] = a[n-i-1];
for(i = 0;i < n;i++)
a[i] = b[i];
对于算法1,不管问题规模多大,总是只需要一个临时变量 t 暂存值即可,因此其空间复杂度为 O(1);对于算法2,采用的是逆序输出原数组到新数组中,之后再覆盖原数组,很显然,随着 n 的增大,新数组要求的存储空间也要增大,所以其空间复杂度为 O(n)。