数据结构java版第1章

《数据结构java版第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法分析1.1算法1.2时间复杂度Big-O1.3思考题11.1算法1.1.1数组元素相加1.1.2矩阵相加1.1.3矩阵相乘1.1.4顺序查找21.1算法算法（Algorithm）是一个解决问题的有限步骤过程，也可以说是在解答过程中的一步步过程。1.1.1数组元素相加数组元素相加是将数组中每个元素的值加起来，其所对应的Java程序如下：publicstaticintsum(intarr[],intn){inti,total=0;for(i=0;i

2、：publicstaticvoidadd(inta[][],intb[][],intc[][],intm,intn){for(inti=0;i

3、][j]=sum;}}51.1.4顺序查找顺序查找是指在一个数组中，由第1个元素开始依次查找，我们假设要找的数据一定在数组中，其程序如下：publicstaticintsearch(intdata[],inttarget,intn){inti;for(i=0;i

4、-O在程序或算法中，每一条语句（statement）的执行时间为：①此语句执行的次数；②每次执行此语句所需的时间。两者相乘即为此语句的执行时间。8Big-O的定义f(n)=O(g(n))，当且仅当唯一存在正整数c及n0，使得f(n)≤cg(n)，对所有的n，n≥n0。上述的定义表示可以找到c和n0，使得f(n)≤c×g(n)，此时，我们称f(n)的Big-O为g(n)。9常见的Big-OBig-O类别O(1)常数时间（constant）O(log2n)对数时间（logarithmic）O(n)线性时间（linear）O(n2log2n)对数线性时间（loglinear）O(n2)平

5、方时间（quadratic）O(n3)立方时间（cubic）)O(2n)指数时间（exponential）O(n!)阶乘时间（factorial）O(nn)n的n次方时间10各种Big-O的比较nlog2nnlog2nn2n32n10011221248442816641683246451225616464256409665536325160102432768429496729611衡量效率的其他方法除了Big-O之外，用来衡量效率的方法还有和，以下是它们的定义。的定义如下：f(n)=(g(n))当且仅当存在正整数c和n0，使得f(n)≥c×g(n)，对所有的n，n≥n0。

6、的定义如下：f(n)=(g(n))，当且仅当存在正整数c1、c2及n，使得c1×g(n)≤f(n)≤c2×g(n)，对所有的n，n≥n0。12二分查找法与顺序查找法的比较数组大小二分查找顺序查找1281024104857642949672967102032128102410485764294967296从上表中的比较可以得知，二分查找法比顺序查找法效率高，那是因为二分查找法的Big-O为log2n，远比顺序查找法的Big-O为n来得好。13斐波纳契序列（Fibonaccinumber）其定义如下：f0=0f1=1fn=fn-1+fn-2当n≥2时因此f2=f1+f0=1+0=1f

7、3=f2+f1=1+1=2f4=f3+f2=2+1=3f5=f4+f3=3+2=5…fn=fn-1+fn-214递归法若以递归的方式进行计算的话，如下图所示：15递归法用递归方式，需计算的项目表如下：n第n项）需计算的项目数011123354951562516递归法Java程序的以递归方式计算斐波纳契序列：intFibonacci(intn){if(n==0)return0;elseif(n==1)return1;elsereturn(Fibonacci(n–1)+F