在评价算法的时间复杂性时,不考虑两算法执行 次数之间的细小区别,而只关心算法的本质差别。为 此,引入一个所谓的O0记号,则 T1()=2n=Om),T2(n)=n+1=O(n) 一个函数是09)的,则一定存在正常数c和 ,使对所有的n>m,都满足fn)<cg(n) 下面的表格给出了一些具体函数的O0的表示,如图 所示。 f(n) o(g(n)) 量级 35 OC 常数阶 2n+7 O(n) 线性阶 O(n2) 平方阶 2n3+n O(m3) 立方阶
在评价算法的时间复杂性时，不考虑两算法执行 次数之间的细小区别，而只关心算法的本质差别。为 此，引入一个所谓的O() 记号，则 T1(n)=2n=O(n),T2(n)=n+1=O(n)。 一个函数f(n)是O(g(n))的，则一定存在正常数c和 m，使对所有的n>m，都满足f(n)<c*g(n)。 下面的表格给出了一些具体函数的O()的表示，如图 所示。 f(n) O(g(n)) 量级 35 O(1) 常数阶 2n+7 O(n) 线性阶 n 2+10 O(n2 ) 平方阶 2n3+n O(n3 ) 立方阶
算法的时间复杂性不仅和问题的规模大小有关, 还与问题数据的初始状态有关。 这样就有了算法在最好、最坏以及在平均状态下的 时间复杂性的概念。 ①算法在最好情況下的时间复杂性是指算法计算量的 最小值。 ②算法在最坏情况下的时间复杂性是指算法计算量的 最大值。 ③算法的平均情况下的时间复杂性是指算法在所有可 能的情况下的计算量经过加权计算出的平均值
算法的时间复杂性不仅和问题的规模大小有关， 还与问题数据的初始状态有关。 这样就有了算法在最好、最坏以及在平均状态下的 时间复杂性的概念。 ①算法在最好情况下的时间复杂性是指算法计算量的 最小值。 ②算法在最坏情况下的时间复杂性是指算法计算量的 最大值。 ③算法的平均情况下的时间复杂性是指算法在所有可 能的情况下的计算量经过加权计算出的平均值
本书在对算法进行分析时,会用到如下两个记号 x1:表示不大于x的最大整数; Lx:表示不小于x的最小整数
本书在对算法进行分析时，会用到如下两个记号： x：表示不大于x的最大整数； x：表示不小于x的最小整数
第2章线性表及其顺序存储 线性表是一种常用的数据结构,本章介绍线性表 及其顺序存储,并对栈和队列及它们的顺序实现给出 了详细的设计描述。 2线性表 线性表是一个线性结构,它是一个含有n20个结 点的有限序列,对于其中的结点,有且仅有一个开 始结点没有前驱但有一个后继结点,有且仅有 终端结点没有后继但有一个前驱结点,其它的结点 都有且仅有一个前驱和一个后继结点。一般地, 线性表可以表示成一个线性序列:k1k2,…kn,其 中k是开始结点,k是终端结点
第2章 线性表及其顺序存储 线性表是一种常用的数据结构，本章介绍线性表 及其顺序存储，并对栈和队列及它们的顺序实现给出 了详细的设计描述。 2.1线性表 线性表是一个线性结构，它是一个含有n≥0个结 点的有限序列，对于其中的结点，有且仅有一个开 始结点没有前驱但有一个后继结点，有且仅有一个 终端结点没有后继但有一个前驱结点，其它的结点 都有且仅有一个前驱和一个后继结点。一般地，一 个线性表可以表示成一个线性序列：k1 ,k2 ,…,kn，其 中k1是开始结点，kn是终端结点
22顺序表 221顺序表 线性表采用顺序存储的方式存储就称之为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组 地址连续的存储单元中。 如顺序表的每个结点占用len个内存单元,用 location(k)表示顺序表中第个结点k所占内存空间的 第1个单元的地址。则有如下的关系 location(+1=location(ki)+len location(ki)=location(k,)+(i-1)len
2.2.1顺序表 线性表采用顺序存储的方式存储就称之为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组 地址连续的存储单元中。 如顺序表的每个结点占用 len个内存单元，用 location (ki )表示顺序表中第i个结点ki所占内存空间的 第1个单元的地址。则有如下的关系 location (ki+1 ) = location (ki ) +len location (ki ) = location(k1 ) + (i-1)len 2.2顺序表