XingtanXue

Java科普之算法剖析

从小白晋升,一路走来;从helloworld,到JFrame,再到Android;从城外小子,到内城的阶梯,站在高耸入云的阶梯上向前望;从迷茫的时代,到苦逼的时代,再到自信的时代;这些路有些艰难,有些坎坷,但–还算顺利;有过困惑,有过烦恼,有过委屈,但一路向前,风雨无阻;前言是遥远的,前方是未知的,前方是广阔的,前方是美好的;我要呼吁广大IT同胞们,让我们向着更遥远、更广阔、更美好的充满未知的未来出发吧!去贪婪的吮吸每一滴“蜜露”,用知识的精髓武装自己,斗志昂扬一如既往的用兴趣开路,去探寻属于自己的一片天地!

今天冒昧给大家讲讲算法的故事。

在从简单的逻辑写起,从完成一个控件、多个控件,走了一条线程、一条进程;到完成一个模块、若干模块,实现界面之间的交互、控件自定义;再到缓存、数据库、网络交互,内存管理、系统调优、架构扩展;最后又回归逻辑、研究算法,研究层与层之间的调用、依赖,抽象、继承、接口、反射等一些基础的概念;简而言之,把最简单的东西做到极致,那牛逼了!

百度解释:算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。(算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度。)
接下来依次讲几个算法,冒泡、选择……

冒泡算法原理:两个两个的比较,其中较大的与较小的换位,每次都能排出剩下数中的最大数,放剩下数的最后;最终排出整齐的数列。

  • 时间复杂度:倒序最大,Cmax=n*(n-1)/2,为T(n^2);正序最小,Cmin=n,为T(n);按实际情况来算。
  • 空间复杂度为:最坏情况,每两个就要换一回,则为n/2+(n-1)/2+……+2/2=n(n+1)/4,Omax=O(n^2);最好情况,已排好,则为O(0)。
  • 代码如下:

public void testBubbleSort() {
int[] sortArray = { 4, 7, 9, 3, 6, 8,11 };
for (int i = 0; i < sortArray.length-1 ; i++) {
boolean isSort = false;
for (int j = 0; j < sortArray.length -1-i; j++) {
if (sortArray[j] > sortArray[j + 1]) {
int temp = sortArray[j];
sortArray[j] = sortArray[j + 1];
sortArray[j + 1] = temp;
isSort = true;
}
}
if (!isSort)
break;
}
System.out.println(Arrays.toString(sortArray));

选择排序原理:第一次,首个与后面的进行比较,把最小的放首位;第二次,次个与后面的进行比较,把次小的放次位;依次进行。

  • 与冒泡的区别在于:选择排序找出最小的下标,然后与此次开始位置数字置换,冒泡需要两个两个的换位置;从这个意义上来说,选择排序占用内存更少,拥有更小的空间复杂度。
  • 时间复杂度:最坏情况,n(n+1)/2,为Tmax=T(n^2);最好情况,已排好,则为T(n)。
  • 空间复杂度;最坏情况为O(n),最好为O(0),分别为正好相反或已排好。
  • 代码如下:

public void testChooseSort() {
int min;
for (int i = 0; i < sortArray.length - 1; i++) {
min = i;
for (int j = i + 1; j < sortArray.length - 1 - i; j++) {
if (sortArray[min] > sortArray[j]) {
min = j;
}
}
if(min!=i){
int temp=sortArray[min];
sortArray[min]=sortArray[i];
sortArray[i]=temp;
}
}
System.out.println(Arrays.toString(sortArray));

其他有趣算法:

如赛马问题

25匹马,5个赛道,如何在不用工具的情况下,找到最快的5匹。问题可以简化为3匹马,3个赛道。

  • 分A B C三组马,各赛一场,结果如下:
  • A1 A2 A3
  • B1 B2 B3
  • C1 C2 C3
  • 3场第1名赛一场,得出第1名
  • 如果是A1,则A2跟B1和C1比1场,其他同理,找出第2名
  • 如果是B1,则A2跟B2和C1比1场,其他同理,找出第3名
  • 比赛结束,共需要6场
  • 同理可算出,25匹马需要10场。

如运煤问题

3000吨煤,用载重1000吨的火车,从原点运往终点,路程1000公里,每公里消耗1吨煤,到终点时煤剩几何?

粗略一算,第一种方案:

  • 第一轮,
  • 第1次,先拉1000吨到A,卸下500吨,返回,行程250公里
  • 第2次,再拉1000吨到A,卸下500吨,返回,行程250公里,同理第三次
  • 第3次后,A地剩下1500吨煤,行程250公里
  • 第二轮
  • 继续第4次,同上,到B地行程187.5公里,每次卸下375吨货物
  • 两轮后,行程437.5公里,剩下货物750吨
  • 第三轮
  • 一次性运到,共剩余312.5吨
  • 分析:由于第三轮每次只运750吨,运量未满,导致最终运送较少。

粗略一算,第二种方案:

  • 第1次,先拉1000吨到A,卸下500吨,行程250公里,返回
  • 第2次,再拉1000吨到A,加上250吨满载,剩下250吨;走250公里到B,卸下250吨,总行程250公里,返回
  • 第3次,再拉1000吨到A,加上250吨满载;再走250公里到B,加上前两次剩下的共500吨,满载1000吨继续,直行到终点,共剩余500吨
  • 分析:似乎比较完美,每次都是满载。

粗略一算,第三种方案:

  • 变下思路,将此题变成n千吨煤,可以走多少公里,即消耗多少
  • 那么1000吨走1000公里,2000吨由于中间要折回+第1次向前走共3次即1000*(1+1/3)公里,同理可得3000吨走
  • 1000(1+1/3+1/5)公里,n千吨可走1000(1+1/3+1/5+……+1/(2n-1))公里
    那么3000公里剩余多少呢?前两句已经讲了3000吨可走的公里,每公里1吨,多出多少公里即多出多少吨
  • 即1000*(1+1/3+1/5)-1000=1600/3吨,即533.33吨。功夫不负有心人,这就是最终答案!

再如扔鸡蛋问题

100层楼,2个蛋,n层楼以下扔下不碎,以上碎,问要扔几次才能确认?

  • 则声明有x次机会,则最多可能尝试的总楼层数为,x+(x-1)+(x-2)+……+1=x*(x-1)/2
    如果100层,则判断小于100即可,结果呢为为14,即至少要扔14次(则从14层开始扔)