算法分析就是对时间复杂性和空间复杂性进行分析时间复杂度概念时间复杂性又叫时间复杂度是对算法运行时间长短的度量。人们通常只考虑三种情况下的时间复杂性最坏、最好、平均情况。计算方法第一步声明哪些代码是基本运算第二步计算时间复杂度第三步写成O(n)的形式注基本运算就是程序中运行最多的最坏的情况空间复杂度概念空间复杂性是对一个算法在运行过程中所占用存储空间大小的度量一般记为S(n)这里的n是问题规模一般不要求计算空间复杂度所以复习一下概念。认识递归方法概念子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己称为递归。直接或间接调用自身的方法成为递归算法。递归的本质函数在调用时首先在栈顶分配他的形式参数和局部变量存储空间然后执行函数函数返回时从栈顶释放他的形式参数和局部变量存储空间而调用他的那个函数的形式参数和局部变量就成为了新的栈顶任何函数运行时都只使用栈顶的那一份存储空间如果递归深度太大栈会溢出——栈式存储管理。举一个具体例子123456789101112longlongfun(intn){if(n 0){printf(Illegal number!\n);return-1;}elseif(n 0)return1;elsereturnn * fun(n - 1);}假如传入n3在栈顶分配fun(3)的局部变量存储空间和他的形式参数然后执行函数由于n1所以会返回3*fun(2)此时fun(2)成为新的栈顶也分配形参和存储空间再次执行函数返回2*fun(1)这时fun(1)成为新的栈顶元素执行后返回结果为1*fun(0)再次执行函数返回fun(0)fun(0)结果为1栈顶的fun(0)分配的空间被释放栈顶变为fun(1)结果为1*11然后被清理栈顶变为fun(2)结果为2*fun(1)2;最后回归到fun(3)结果为3*fun(2)6这就是计算机中本质上递归的过程是通过调用堆栈完成递归的递推和回归过程的。基本的数据结构线性表线性表时最简单、常用的一种数据结构简言之一个线性表时n(n0)个数据元素的有限序列。线性表分为顺序表和链表两种而这最大的区别就是顺序表是顺序存储的链表是随机存储。顺序表把线性表的元素按逻辑次序依次存放在一组地址连续的存储单元用这种方法存储的线性表简称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。顺序表的存储特点是只要确定了起始位置表中任一元素的地址都通过下列公式得到LOCaiLOCa1i-1*L 1≤i≤n 其中L是元素占用存储单元的长度。由于高级程序设计语言中的数组类型也有随机存取的特性因此通常采用数组来描述顺序表。链表链表是线性表的另一种存储与方式其特点是用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的它由一系列结点链表中的每一个元素称为结点组成结点可以在运行时动态生成。链表的主要形式有单链表、循环链表、和双向链表。(1)在线性链表中每个结点包括两个部分:一个是存储数据元素信息的数据域;另一个是存储直接后继存储位置的指针域该域表示了元素与其直接后继元素之间的逻辑关系域中存储的信息称做指针或链。n个结点链接成一个链表即为线性表的链式存储结构。 由于此链表的每个结点中只包含一个指针域故称为线性链表或单链表。 用链表来表示线性表时数据元素之间的逻辑关系是由结点中的指针指示的逻辑上相邻的两个元素其存储的物理位置不要求紧邻。因此在使用链表时人们关心的是它所表示的线性表中数据元素的逻辑顺序而不是每个数据元素在存储器中的实际位置。那么如何设计链表的逻辑结构图呢?通常把链表画成用箭头相链接的结点的序列结点之间的箭头表示链域中的指针。例如线性表的逻辑结构图其中H称为头指针它指示链表中第一个结点的存储位置整个链表的存取必须从头指针开始进行。由于最后一个元素a3没有直接后继因此他的指针域设为空NULL。栈与队列栈与队列时另外两种重要的线性结构他们可以使用上面所讲的顺序表或者链表的结构来最终实现。栈栈可看成是一种“特殊”的线性表该线性表限定仅在 表尾进行插人和删除操作。栈主要应用于表达式的计算、子程序嵌套调用递归调用等。栈具有下述特殊的性质:(1)通常称插入、删除的这一端为栈顶(Top);另一端称为栈底( Bottom)。(2)当表中没有元素时称为空栈。(3)栈的修改是按“后进先出”的原则进行因此栈简称为LIFO表(LastInFirstOut)。每次删除(退栈)的总是当前栈中“最新”的元素即最后插人 (进栈)的元素而最先插人的元素是被放在栈的底部要到最后才能删除。队列和栈相反队列是一种先进先出(First In First Out,FIFO)的线性表它只允许在表的端进行插人元素 而在另端删除元素。队列有下述特殊性质:(1)允许删除的一端称为队头(Front)。(2)允许插人的端称为队尾(Rear)。(3)当队列中没有元素时称为空队列。(4)队列的结构特点是先进队的元素先出队。(5)队列的修改时依先进先出的原则进行的。新来的成员总是加入队尾每次离开的成员总时队头元素而不允许中途离队。