中所需要的基本运算次数。?通常记作:?常见的时间复杂度有:(2)空间复杂度是指执行该算法所需要的内存空间。具体包括(1)算法程序所占的空间;(2)输入的初始数据所占的存储空间;(3)算法执行过程中的额外空间*二、数据结构1.数据结构的基本概念数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。?在此概念中:?(1)数据是指所有能输入到计算机中并被计算机程序处理的符号的总称;?(2)数据元素是指数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理;?(3)一个数据元素可以由若干个数据项组成,数据项是数据的最小单位。*数据结构有三个方面的内容:数据的逻辑结构、数据的存储结构、数据的运算。2.数据的逻辑结构数据的逻辑结构是指数据元素之间的逻辑关系,从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。数据的逻辑结构的表示方法?表示数据的逻辑结构时必须表示清楚两个关键点,一个是数据元素的集合D,另一个是数据元素之间的前后关系R。?表示数据结构的方法有两种:二元关系表和图形表示方法。*A.二元关系表示方法:一个数据结构可以表示为B=(D、R),其中R用二元组来表示(a、b)。a表示前件,b表示后件。?例如,一年四季的数据结构可以表示成:??B=(D、R)?D={春,夏,秋,冬}??R={(春,夏),(夏,秋),(秋,冬)}B.在图形表示方法中,用中间标有元素值的方框来表示数据元素,称为数据结点,简称为结点;用一条有向线段从前件结点指向后件结点(注意:有时可以省略箭头)来表示元素之间的前后关系。*例如,同样是一年四季的数据结构,若用图形方法表示则如图所示。数据的逻辑结构一般分为两种:线性结构和非线性结构。?线性结构:有且只有一个根结点;每一个结点最多有一个前件,也最多有一个后件。如:一年四季。?非线性结构:线性以外的数据结构。如:反映家庭成员间辈分关系的数据结构。
全文预览
