埃拉托色尼素数筛法与二分查找

今天来介绍两种著名的算法——埃拉托色尼素数筛法和二分查找

 

在开始之前，我们先来普及一个记录一种算法所需时间的计法：大O时间复杂度计算法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。

例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法， 这个运行时间为O(n)。单位为什么不是秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数，它指出了算法运行时间如何随着输入的增长而增长的。

注意，大O表示法中不会出现任何除了指数之外的常数，因为任何恒量对于计算机的算力来说都是可以忽略的。比如O(1000n) 其实等价于 O(n)。但其绝不等同于O(n2)或O(log n)

比如这样一段代码：

def a(n: int) -> int:
    return 1

该函数所用的时间不随n的变化而变化，我们称这个函数的时间复杂度为O(1)。

再如：

def b(n: int) -> list:
    array = []
    for i in range(1, n+1):
        array.append(i)
    return array

该函数所用的时间与n的大小理论上成正比，我们称这个函数的时间复杂度为O(n)。

提示：下列两种算法的时间复杂度都带有log，请各位读者务必先学习对数的基本内容再继续。

不知大家听懂了没有，我们先来介绍埃拉托色尼素数筛法。

挨拉托色尼素数筛法

埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数。

步骤：

1. 因为编程语言中数组有下标0，所以需要生成一个长度为n+1的数组

2. 将所有元素暂且标记为指数

3. 把1删除，因为1既不是质数，也非合数

4. 读取数组中最小数2，并保留。删去所有2的倍数

5. 读取数组中最小数3，并保留。删去所有3的倍数

6. ...

7. 重复上述步骤直到范围内的所有数都被标记为保留或删除

时间复杂度：O(n log log n)这个大家有兴趣去搜索一下，较为复杂，这里不进行解释。

题目：请求出所有小于等于n的素数的个数

代码（语言：Go）：

func countPrimes(n int) (cnt int) {
    flags := make([]bool, n+1) // 步骤1
    for i := 2; i <= n; i++ {
        flags[i] = true // 步骤2
    }
    for i := 2; i*i <= n; i++ { // 循环从2开始，代表步骤3
        if flags[i] { // 如果当前数是保留
            // 遍历数组中当前数的倍数，注意这里是从i的平方开始的
            // 因为i * 2 一定能被2整除，i * 3 一定能被3整除
            // 所以所有小于i的平方的i的倍数都一定已被删除
            for j := i; j*i <= n; j += 1 {
                if flags[j*i] { // 如果当前数的某个倍数已被标记为删除，不进行处理
                    flags[j*i] = false // 把所有当前数的倍数标记为删除
                }
            }
        }
    }
    // 计算出现了多少个质数
    for i := range flags {
        if flags[i] {
            cnt++
        }
    }
    // 返回结果
    return
}

来一个猛一点的，比方n = 100000000（1亿），计算一下上述代码的消耗时间：

func main() {
    time1 := time.Now().UnixNano()
    fmt.Println(primes(100000000))
    time2 := time.Now().UnixNano()
    fmt.Printf("primes: %.3fms\n", float64(time2-time1)/1000000)
}

输出：

5761455
primes: 795.643ms

消耗了0.8秒，100000000以下的质数有5761455个。

为了进行对比，我又用传统办法写了一版，代码不展示，主要思路是计算每个数是不是质数，再计数，这种方法耗时2600s，即43分钟左右，埃氏筛法的速度是后一种筛法的3000倍，可见其高效。

但是，埃氏筛法并不是最快的素数筛法，还有两种素数筛法，这里不做详细介绍

1. 基于埃氏筛法改进的时间复杂度为O(n)的欧拉筛法。实际运行速度与埃氏筛法相去不远。

2. 时间复杂度为O(n0.75)的究极筛法（这种筛法的创始者名字不详）。这种方法本人试过，速度大约是埃氏筛法的100倍。不过由于本人才疏学浅，至今没有理解其原理。

二分查找

用于在一个排好序的数组里快速查找一个数的位置

比如这样一个数组：[1, 2, 4, 7, 9, 10]

如何查找9的位置？

听起来很简单，从1开始一个一个往下找呗？这种顺序查找算法时间复杂度为O(n)，在本例中，其比较了9次找到

但是，二分查找的时间复杂度是O(log n)。

具体思想也很简单：

1. 找出数组中间项，由于这里有6个数，不妨设为4

2. 比较4与要查找的数9的大小，注意到 9 > 4

3. 把数组缩小为[4, 7, 9, 10]

4. 取中间项7

5. 注意到9 > 7

6. 把数组缩小为[9, 10]

7. 取中间项9

8. 注意到9 = 9

9. 完成

比较了3次

没少比较几次，对吧。

设想一个长为1000000的数组，顺序比较最倒霉可能要比较1000000次，而二分算法最倒霉只用比较20次，这样是不是就相当快了？

具体代码：

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for right > left {
        // 下面这一行等价于 mid := (left + right) / 2
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if nums[left] != target {
        return -1
    }
    return left
}