計算量とオーダー記法ランダウの記法、素数判定、平方根、二分探索、指数関数、対数関数、年齢当てゲーム

学習環境

開発環境

問題解決力を鍛える!アルゴリズムとデータ構造 (大槻兼資(著)、秋葉拓哉(監修)、講談社)の第2章(計算量とオーダー記法)、章末問題2.3、2.4、2.5の解答を求めてみる。

2.3

\begin{array}{l} p^{2} \leq N \\ p \leq \sqrt{N} \\ O (\sqrt{N}) \end{array}

2.4

\begin{array}{l} 2^{n} = 2^{k} \\ n = k \end{array}

よってk回で当てられる。

2.5

\begin{array}{l} 2^{k} = N \\ k \log 2 = \log N \\ k = \frac{1}{\log 2} \log N \end{array}

よって、

O (\log N)

実際に確認してみる。

コード

package main

import (
	"fmt"
	"math"
)

func primeON(n int) int {
	count := 0
	if n <= 1 {
		return count
	}
	for p := 2; p*p <= n; p++ {
		count++
		if n%p == 0 {
			return count
		}
	}
	return count
}
func main() {
	for n := 2; n <= 50; n++ {
		fmt.Println(n, primeON(n), math.Sqrt(float64(n)))
	}
}

入出力結果

% go run ./main.go
2 0 1.4142135623730951
3 0 1.7320508075688772
4 1 2
5 1 2.23606797749979
6 1 2.449489742783178
7 1 2.6457513110645907
8 1 2.8284271247461903
9 2 3
10 1 3.1622776601683795
11 2 3.3166247903554
12 1 3.4641016151377544
13 2 3.605551275463989
14 1 3.7416573867739413
15 2 3.872983346207417
16 1 4
17 3 4.123105625617661
18 1 4.242640687119285
19 3 4.358898943540674
20 1 4.47213595499958
21 2 4.58257569495584
22 1 4.69041575982343
23 3 4.795831523312719
24 1 4.898979485566356
25 4 5
26 1 5.0990195135927845
27 2 5.196152422706632
28 1 5.291502622129181
29 4 5.385164807134504
30 1 5.477225575051661
31 4 5.5677643628300215
32 1 5.656854249492381
33 2 5.744562646538029
34 1 5.830951894845301
35 4 5.916079783099616
36 1 6
37 5 6.082762530298219
38 1 6.164414002968976
39 2 6.244997998398398
40 1 6.324555320336759
41 5 6.4031242374328485
42 1 6.48074069840786
43 5 6.557438524302
44 1 6.6332495807108
45 2 6.708203932499369
46 1 6.782329983125268
47 5 6.855654600401044
48 1 6.928203230275509
49 6 7
50 1 7.0710678118654755
%