练习 1.24

要完成这道练习,我们首先需要将书本 34 页的 fast-prime? 程序敲下来:

;;; p34-fast-prime.scm

(load "p34-expmod.scm")

(define (fermat-test n)
    (define (try-it a)
        (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
    (cond ((= times 0)
            true)
          ((fermat-test n)
            (fast-prime? n (- times 1)))
          (else
            false)))
;;; p34-expmod.scm

(define (expmod base exp m)
    (cond ((= exp 0)
            1)
          ((even? exp)
            (remainder (square (expmod base (/ exp 2) m))
                       m))
          (else
            (remainder (* base (expmod base (- exp 1) m))
                       m))))

然后,使用一个新文件,先载入 练习 1.22search-for-primes 函数,再载入 fast-prime? 函数,然后重定义 prime? 函数,让它使用 fast-prime? 函数而不是原来的平方根复杂度的算法,当 search-for-primes 调用 prime? 进行素数检测的时候,使用的就是费马检测算法:

;;; 24-search-for-primes.scm

(load "22-search-for-primes.scm")
(load "p34-fast-prime.scm")

(define (prime? n)
    (fast-prime? n 10))

现在,可以对使用新算法的 search-for-primes 进行测试了:

1 ]=> (load "24-search-for-primes.scm")

;Loading "24-search-for-primes.scm"...
;  Loading "22-search-for-primes.scm"...
;    Loading "22-continue-primes.scm"...
;      Loading "p33-prime.scm"...
;        Loading "p33-smallest-divisor.scm"...
;          Loading "p33-divides.scm"... done
;          Loading "p33-find-divisor.scm"... done
;        ... done
;      ... done
;      Loading "22-next-odd.scm"... done
;    ... done
;  ... done
;  Loading "p34-fast-prime.scm"...
;    Loading "p34-expmod.scm"... done
;  ... done
;... done
;Value: prime?

1 ]=> (search-for-primes 1000)      ; 一千
1009
1013
1019
are primes.
;Value: 1

1 ]=> (search-for-primes 10000)     ; 一万
10007
10009
10037
are primes.
;Value: 3

1 ]=> (search-for-primes 100000)    ; 十万
100003
100019
100043
are primes.
;Value: 3

1 ]=> (search-for-primes 1000000)   ; 一百万
1000003
1000033
1000037
are primes.
;Value: 4

可以看到,新的 search-for-primes 比起 练习 1.22search-for-primes 在速度上有所改进,但是当 search-for-primes 的输入增大一倍的时候,计算所需的时间并不是按预期的那样,严格地按常数增长,比如计算 (search-for-primes 1000000) (一百万)的速度就比计算 (search-for-primes 1000) (一千)的速度要慢 4 倍。

运行时间、步数和算法复杂度

通过对 练习 1.22练习 1.23练习 1.24 (本题)的三个版本的 search-for-primes 进行测试,我们发现,使用算法复杂度或者计算步数并不能完全预测程序的运行时间 —— 的确如此。

首先,即使我们能准确地计算出程序所需的步数,程序的运行速度还是会受到其他条件的影响,比如计算机的快慢,系统资源的占用情况,或者编译器/解释器的优化程度,等等,即使是同样的一个程序,在不同情况下运行速度也会有所不同,所以程序的计算步数能对程序的运行状况给出有用的参考信息,但是它没办法、也不可能完全准确预测程序的运行时间。

另一方面,算法复杂度比计算步数更进一步,它无须精确计算程序的步数 —— 算法复杂度考虑的是增长速度的快慢:比如说,当我们说一个算法 A 的复杂度比另一个算法 B 的复杂度要高的时候,意思是说,算法 A 计算所需的资源(时间或空间)要比算法 B 要多。

一般来说,复杂度更低的算法,实际的运行速度总比一个复杂度更高的算法要来得更快,有时候在输入比较小时会比较难看出差别,但是当输入变得越来越大的时候,低复杂度算法的优势就会体现出来。

举个例子, 练习 1.22search-for-primes 程序的复杂度就是 \(\Theta(\sqrt{n})\) ,而在本题给出的 search-for-primes 的复杂度就是 \(\Theta(\log n)\) ,我们可以预期,本题给出的 search-for-primes 总比 练习 1.22search-for-primes 要快。

先来测试 练习 1.22search-for-primes

1 ]=> (load "22-search-for-primes.scm")

;Loading "22-search-for-primes.scm"...
;  Loading "22-continue-primes.scm"...
;    Loading "p33-prime.scm"...
;      Loading "p33-smallest-divisor.scm"...
;        Loading "p33-divides.scm"... done
;        Loading "p33-find-divisor.scm"... done
;      ... done
;    ... done
;    Loading "22-next-odd.scm"... done
;  ... done
;... done
;Value: search-for-primes

1 ]=> (search-for-primes 10000) ; 一万
10007
10009
10037
are primes.
;Value: 1

1 ]=> (search-for-primes 100000000) ; 一亿
100000007
100000037
100000039
are primes.
;Value: 73

1 ]=> (search-for-primes 1000000000000) ; 一万亿
1000000000039
1000000000061
1000000000063
are primes.
;Value: 7679

再来测试本题的 search-for-primes

1 ]=> (load "24-search-for-primes.scm")

;Loading "24-search-for-primes.scm"...
;  Loading "22-search-for-primes.scm"...
;    Loading "22-continue-primes.scm"...
;      Loading "p33-prime.scm"...
;        Loading "p33-smallest-divisor.scm"...
;          Loading "p33-divides.scm"... done
;          Loading "p33-find-divisor.scm"... done
;        ... done
;      ... done
;      Loading "22-next-odd.scm"... done
;    ... done
;  ... done
;  Loading "p34-fast-prime.scm"...
;    Loading "p34-expmod.scm"... done
;  ... done
;... done
;Value: prime?

1 ]=> (search-for-primes 10000) ; 一万
10007
10009
10037
are primes.
;Value: 2

1 ]=> (search-for-primes 100000000) ; 一亿
100000007
100000037
100000039
are primes.
;Value: 4

1 ]=> (search-for-primes 1000000000000) ; 一万亿
1000000000039
1000000000061
1000000000063
are primes.
;Value: 9

1 ]=> (search-for-primes 1000000000000000)  ; 一千万亿
1000000000000037
1000000000000091
1000000000000159
are primes.
;Value: 24

可以看到,当输入比较小时,两个算法的速度差不多,但是随着输入越来越大,低复杂度算法的优势就会凸显出来。

讨论

blog comments powered by Disqus