数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。
把 **具体存储结构上的操作实现方法** 称为算法。
确切地说,算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令包含一个或多个计算机操作。
一个算法具有如下特性:
我们有许多方法来描述一个算法,如:
设计一个算法:求解一元二次方程组
ax^2+bx+c=0
我们分别用文字描述和 C/C++语言来描述设计的算法:
void solution(float a, float b, float c){
float d, x1, x2, x;
d = b\*b - 4\*a\*c;
if(d>0){
x1 = (-b + sqrt(d)) / (2\*a);
x2 = (-b - sqrt(d)) / (2\*a);
printf("两个实根是:x1=%f, x2=%f\n", x1, x2);
}
else if(d==0){
x = (-b) / (2\*a);
printf("一个实根是:x=%f\n", x);
}
else{
printf("不存在实根\n");
}
}
从上面的两个例子我们可以看出用 C/C++来描述的算法结构更清晰(编写的程序结构化更高,对 d的三种不同情况的处理一目了然)。
在一个算法设计好后,还需要对其进行分析来确定一个算法的好坏。
通常由两种衡量算法效率的方法:事后统计法和事前分析估算法。
事后分析法存在以下缺点:
所以我们一般采用事前分析法。
一般来说,一个程序的运行速度不仅和算法有关,还和运行程序的计算机和所处计算机环境有关。所以我们需要撇开这些计算机软件、硬件有关的因素,仅考虑算法本身的效率高低。
一个算法是由控制结构(顺序、分支和循环)和原操作(固有的数据类型的操作,或者可以理解为分支和循环里要执行的操作)构成的。
为了比较同一问题的不同算法,通常从算法中选取一种对所研究的问题来说是基本运算的原操作,算法执行的时间大致为原操作的执行时间和被执行的次数的乘积。
显然,在一个算法中,执行原操作的次数越少,其运行时间也就相对地越少;执行的原操作次数越多,其运行时间也就相对地越多。
所以通常把算法中执行原操作地次数称为算法地时间复杂度,也就是说,一个算法地时间复杂度就是指其原操作在算法中反复执行的次数。
算法中基本运算次数(原操作)T(n)是问题规模 n的某个函数,记作:
T(n)=O(f(n))
"O"的定义为:若 f(n)是正整数 n的一个函数,则 T(n)=O(f(n))表示存在一个正整数 M,使得当 n>=n0时都满足
|T(n)|\leq M|f(n)|
也就是说,我们只需要求出 f(n)的最高阶,而忽略其低阶项和常系数,例如:
O(3n^3+2n^2+n+1) \leftrightarrow O(n^3)
一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。
在对算法进行存储空间分析时,只考虑辅助变量所占空间。所以,空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度。
与时间复杂度类似,空间复杂度也是问题规模 n的函数,也以数量级的形式给出,记作:
S(n)=O(g(n))
若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作或就地工作。若所需存储量依赖于输入,则通常按最坏的情况考虑。
转载自:
数据结构教程(第二版)
李春葆 等 编著
清华大学出版社
ISBN:978-7-302-14229-4
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。