java算法：算法分析事例

java算法：算法分析事例

假设：有N个银行卡，给定M个交易中任一笔交易是否涉及到该N个银行卡中的任意一张。（针对该运用，N可能很大，M可能巨大。估算目标运行时间。）

例一：顺序查找

public static int sequentialSearch(int a[], int v, int s, int r){
    int i;
    for( i = s; i <= r; i++){
        if(v == a[i]){
            return i;
        }
    }
    return -1;
}

public static int sequentialSearch(int a[], int v, int s, int r){
	int i;
	for( i = s; i <= r; i++){
		if(v == a[i]){
			return i;
		}
	}
	return -1;
}

该方法检查v是否在先前存储的数a[s],a[s+1],...,a[r]中，方法从头开始造，依次与每个数进行比较。顺序查找对每个不成功的查找都要检查N个对象，对于成功查找平均约检查N/2个对象。

例二：折半查找

public static int binarySearch(int a[], int v, int s, int r){
    while(r >= s){
        int m = (s + r)/2;
        if(v == a[m]){
            return m;
        }
        if(v < a[m]){
            r= m - 1;
        }else{
            s = m + 1;
        }
    }
    return -1;
}

public static int binarySearch(int a[], int v, int s, int r){
	while(r >= s){
		int m = (s + r)/2;
		if(v == a[m]){
			return m;
		}
		if(v < a[m]){
			r= m - 1;
		}else{
			s = m + 1;
		}
	}
	return -1;
}

折半查找，前提是表中的数据是有序的（如：从小到大）。折半查找要检查的对象个数不会超过floor(lgN) + 1。注：floor()向下取整，ceil()向上取整，round()四舍五入。

当N翻倍的时候，折半查找的运行时间几乎没有变化，但是，顺序查找的运行时间却增加了一倍。显然，随着N的增长，对于巨大的M，顺序查找是不可行的，但是折半查找执行的速度确是不错的。