第一讲 算法引论

《第一讲 算法引论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一讲算法引论java程序有两种类型：应用程序和applet。应用程序一定有一个主方法main，而applet的主方法为initjava的applet必须嵌入到HTML文件中，由Web浏览器或applet阅读器来执行。对于非基本数据类型要使用new语句来建立。如:建立数据类型为String的对象：Strings;s=newString(“Welcome”);或trings=newString(“Welcome”);在Java语言中，执行特定任务的函数或过程称为方法(methods)。方法的参数个数

2、以及各参数的类型定义了该方法的签名。在java中允许方法重载，即允许定义方法有不同签名的同名方法。Java的异常(exception)机制，提供了一种简洁的错误处理方法。当程序发现一个错误时，就引发一个异常，以便在程序最合适的地方捕获异常，并进行处理。java的new运算用于分配所需的内存空间。如：int[]a=newint[500000];à便于java的垃圾回收器回收不使用的内存，可用语句a=null;算法的复杂性有时间复杂性与空间复杂性之分。算法设计追求的目标是设计出复杂性尽可能低的算法。它

3、们依赖于所解决问题的规模N、算法输入I、算法本身A。第二讲递归与分治策略排列问题publicstaticvoidperm(Object[]list,intk,intm){//产生list[k,m]的所有全排列if(k==m){//单元素序列for(i=0;i<=m;i++)System.out.print(list[i]);System.out.println();}else//多元素序列。递归产生排列for(i=0;i<=m;i++){MyMath.awap(list,k,i);perm(lis

4、t,k+1,i);MyMath.awap(list,k,i);}}递归算法结构清晰、可读性强，而且容易用数学归纳法证明其正确性，因此为设计算法带来很大方便性。¡运行效率较低，耗费时间与空间都比非递归算法要多。¡有时可以通过在递归算法中消除递归，使其转化为非递归算法。二分搜索技术:计算时间复杂性为O(logn)publicstaticintbinarySearch(int[]a,intx,intn){intleft=0;intright=n-1;while(left<=right){intmiddl

5、e=(left+right)/2;if(x=a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;//未找到}合并排序基本思想:是将待排序的元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。T(n)=O(nlogn)。publicstaticvoidmergeSort(Comparable[]a,intleft,intright){

6、Comparable[]b=NewComparable[a.length];if(left

7、m,intr){//合并c[l:m]和c[m+1:r]到d[l,r]inti=l,j=m+1,k=l;while((i<=m)&&(j<=r))if(c[i].compareTo(c[j])<=0)d[k++]=c[i++];elsed[k++]=c[j++];if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q];elsefor(intq=i;q<=m;q++)d[k++]=c[q];}合并排序算法改进publicstaticvoidmergeSort(Comparable

8、[]a){Comparable[]b=NewComparable[a.length];ints=1;while(s