算法 概述

2019, Apr 29    

算法-概述

1.算法思想

  1. 穷举法
  2. 递推法：有明显公式规律
  3. 递归法
  4. 分治法：把大问题划分成小问题
  5. 概率法：将问题转化为面积问题，然后随机撒点

2.常见算法

  • 排序算法

  • 查找算法

    • 顺序查找

    • 折半查找

      int binarySearch(int R[], int low, int high, int k){
	int mid = 0;
	while(low <= high){
		mid = (low + high)/2;
		if (R[mid] == k) return mid;
		else if (R[mid] > k) high = mid-1; // k位于mid位置的左边，high调整
		else low = mid+1; // k位于mid位置的右边，low调整
	}
	return 0;
}

3.基本数学问题

3.1. 求最大公约数

  • 辗转相除法

    public int greatestCommonDivisor(int a, int b) {
    int m, n, r;
    if (a > b) {
        m = a;
        n = b;
    } else {
        m = b;
        n = a;
    }
    // 辗转相除
    r = m % n;
    while (r != 0) {
        m = n;
        n = r;
        r = m % n;
    }
    return n; // 最大公约数
}
3.2. 求最小公倍数
public int leastCommonMultiple(int a, int b) {
    return (a * b) / greatestCommonDivisor(a, b);
}
3.3. 判断素数

素数：大于1，且只能被1和自身整除的数

合数：大于1的非素数

0和1既不是素数也不是合数

  • 根据定义判断

    public boolean isPrime(int num) {
    for (int i = 0; i < num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

  • 判断从2到sqrt(n)是否存在其约数，时间复杂度O(sqrt(n))

    public boolean isPrime(int num) {
	for (int i = 2; i <= Math.sqrt(num); ++i) {
		if (num % i == 0) {
			return false;
         }
    }
    return true;
}

    扩展：

    方式1：判断2之后，就可以判断从3到sqrt(n)之间的奇数了，无需再判断之间的偶数，时间复杂度O(sqrt(n)/2)

    方式2：大于等于5的质数一定和6的倍数相邻 ，时间复杂度O(sqrt(n)/3)

# Data Structure