ǡ¤ǤȤŪõǡȰפܤõФƤȤǡõȤǡοʤñõƤäƤ褤Ϲ®ˡͤʤФʤʤ
õˡȤϡǡǽ餫֤ˤҤȤĤӤơŪΥǡõФ르ꥺǤ롣ǡõǤäȤñˡǤ롣õФǡϡ¤ǤƤõǤ롣
õˡǤϡΤ褦ʥ르ꥺõԤ
1ǽA(1)ϤơõǡXȽӤ롣
2A(k)õǡXȰפ硢kܤӤõλ롣
3A(k)1knϰϤǥǡXȰפʤ硢nkȤʤäƥ롼פλ롣
㡧10ĤΥ桼̾ܤƤƥȥե뤫顢õˡȤäõǡǤipusironפõƤ
Ǥ7ܤӤŪΥ桼̾õλǤ롣
õԤݤˡפǡ¸ߤʤνλȤơκǸõǡղä뤳Ȥ롣ղǤΤȤʼڤФؤȤǡnʤСn+1ܤʼ֤櫓Ǥ롣
㡧ۤɤʼ֤
ʤʼʤɤȤΤͤΤȤȡʼѤʤȤ롼פνꡢʤ뤫Ǥ롣
ƵΤ褦롣
õԤ르ꥺͤ롣
1 2 3 4 5 6 |
|
ǡnΤȤõϼ̤Ǥ롣
õˡǤϼ¹Ի֤ǿn㤹Τǡ̤ΥǤ롣
õˡ¹Ԥ륢르ꥺLSearchåɤȤͼ¸Ƥߤ롣¸ѤΥץLinearSearch.javaˤϡ餫data˥åȤͤ椫顢ǻꤷͤõץǤ롣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| - | | | | | - - - | | ! ! | | ! | | - | | | - | | - | - | | ! | | | | | - | ! | | | | | | - | - | ! ! ! |
|
¹ϼΤ褦ˤʤ롣
>java LinearSearch 67 data[0] = 55 data[1] = 10 data[2] = 20 data[3] = 42 data[4] = 98 data[5] = 71 data[6] = 28 data[7] = 40 data[8] = 67 data[9] = 99 67ֹ8Ǥ >java LinearSearch 56 data[0] = 55 data[1] = 10 data[2] = 20 data[3] = 42 data[4] = 98 data[5] = 71 data[6] = 28 data[7] = 40 data[8] = 67 data[9] = 99 56ϸĤޤǤ
ʼѤõˡΥץ˽ˤϡLSearchåɤΤ褦˽Ф褤
ޤץdataκǸ0ɲä롣
data = new int[] {55,10,20,42,98,71,28,40,67,99,0}; //Ǹ0ɲ
ХʥꥵʬˡȤϡõϰϤ2ʬõϰϤơǽŪΥǡĤФˡǤ롣ǡϾ礫߽ƤʤФʤʤ
ХʥꥵǤϡΤ褦ʥ르ꥺõԤ
1ޤǽˡƬ1nͤбǡǡˤȡõǡXȤӤ롣
2õǡXǤ礭ϡǤ礭ʥǡǤӤ롣õǡXǤ꾮ϡǤ꾮ʥǡǤӤ롣
3A(k)1knϰϤǥǡXȰפʤ硢nkȤʤäƥ롼פλ롣
㡧
õоݤ֤¤ǤΤǡƬõΤǤϤʤ椫õõƤͤˤõλǤ롣ʤС¦¦Τ줫Ǥ롣ͤ⾮к¦礭б¦Ȥʤ롣ȡõʤФʤʤǡο쵤ȾʬˤʤäƤޤ櫓Ǥ롣줬ХʥꥵᤤͳǤ롣
ƵΤ褦롣
1 2 3 4 5 6 7 8 9 |
|
ǡnΤȤӲϼ̤Ǥ롣
Binary-Search(S,k,p,r)η̤ϼΤ褦ˤʤ롣
Master TheoremȤСΤ褦˷Ǥ롣
äơХʥꥵη̤ΥǤ롣
㡧Ģ100ܤȤ¿Ȥ20ǥǽȤȤˤʤ롣
õˡμ¸ǻȤäJavaץõˡåɤХʥꥵåɤѹƤߤBinarySearch.javaˡǡƱ10Ǥ뤬ͤϾ¤٤ޤõl,m,rͤõɽ褦ˤƤ롣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| - | | | | | - | | | | | - | | | | | | - | - | - | ! ! | | | ! | | - | | | - | | - | - | | ! | | | | | - | ! | | | | | - | - | ! ! ! |
|
¹Է̤ϼ̤Ǥ롣
> java BinarySearch 99 data[0] = 10 data[1] = 20 data[2] = 28 data[3] = 40 data[4] = 42 data[5] = 55 data[6] = 67 data[7] = 71 data[8] = 98 data[9] = 99 1:l=0 m=4 r=9 2:l=5 m=7 r=9 3:l=8 m=8 r=9 4:l=9 m=9 r=9 99ֹ9Ǥ
õˡʤ99õΤ˺ǰ10õʤФʤʤХʥꥵǤ¿Ƥ4õǤ롣ʤʤС1024ʡ16ˤǤ롣
MathematicaǥХʥꥵδؿǤBinarySearch[list,elem]ȼΤ褦˥ɤˤʤ롣
1 2 3 4 5 6 7 8 9 |
|
[]Possible spelling errorפȤ顼ɽ뤫⤷ʤlistΥڥ뤬Listδְ㤤ǤϤʤMathematica¦ڤ˶Ƥ줿˲ʤΤǡ̵뤷Ƥʤ
㡧Τ褦˼¹ԤȡꥹȤ{1,3,5,7,9}ʥȺѤߤǤ뤫OKˤͿơ7õȡ4ܤˤȤȤ狼롣ޤ10õȡ0ɽ¸ߤʤȤ狼롣
ۤɤδؿBinarySearch[list,elem]ˡ르ꥺư뤿Pring[]ޥɤ롼ΤؿBinarySearch2[list,elem]Ȥ롣
1 2 3 4 5 6 7 8 9 10 11 |
|
㡧n0n1κǽȳȿθͤƤߤ롣5õȤϡ3ܤȯƤ롣10Τ褦ǤʤȤϡ르ꥺ礭ʲȿפƤ뤳Ȥ狼롣
ؿBinarySearch[list,elem]ˡAppendTo[]ޥɤ뤳ȤǺǽŪ˥ꥹȤϤ褦˲¤롣BinarySearch3[list,elem]Ȥ롣
1 2 3 4 5 6 7 8 9 10 11 |
|
ɤΤ褦˶֤ʤޤƤ뤫եɽȻפ
1ޤ1100,000ޤǤƤꥹlʾʸΥˤ롣
l=Range[100000];
2ꥹl¸ߤʤʤǤ7500.5ˤõ롣
pairs=BinarySearch3[l,7500.5]
̤Ȥõn0n1ΥڥΥꥹȤФ롣
{{1,100000},{1,49999},{1,24999},{1,12499},{6251,12499}, {6251,9374},{6251,7811},{7032,7811},{7422,7811},{7422,7615}, {7422,7517},{7470,7517},{7494,7517},{7494,7504},{7500,7504}, {7500,7501},{7501,7501},{7501,7500}}
3õƤ֤бĹ롣(n0,i-1/2)ǡ夬(n1,i)Ǥ롣
Table[Rectangle[{pairs[[i,1]],-i+1/2},{pairs[[i,2]],-i}], {i,Length[pairs]} ];
4ǸShowޥɤĹɽ롣
Show[Graphics[%], Axes->None, Frame->True, AspectRatio->1/3, PlotRange->All];
ϤϼΤ褦ˤʤäơ֤ʤǤɤΤ褦ȾʬˤʤäƤ狼롣
ϥåˡʥϥåɽõϡǡ®õ뤿ˡΤҤȤĤǡǡǼݤˤΥɥ쥹ϥåؿǷ롣ϥåؿǷ줿ͤΤȤϥåȤΥϥåͤѤ뤳Ȥǡǡõݤˤ֤ṳ̂뤳ȤǤ롣
㡧äñˤ뤿ˡϥåؿmod 10Ƿ1ץ饹ؿȤ롣ϥåɽκǸH(10)ȤƤΤǡǡ+11ܤܤƹͤΤǤϤʤǡ1ܤܤƤ1äȤƹͤ롣
ϥåˡϤ餫ϥåؿѤƳǼ֤ƤΤǡǡФۤ1ӤõФȤǤ롣
ǡǼȤˡۤʤǡƱϥåͤƤ뤳Ȥ͡ʥꥸˤ뤤ϥΥ˥Ȥ˳ǼƤ쥳ɡʥǡˤۡ쥳夫Ǽ줿ʾͤΤ˳ǼǤʤ˥쥳ɡʥǡˤΥ˥쥳Ȥ
褹륢ץ2̤ꤢ롣
ԤΥץȤơSHA256ʤɤȤФȤꤢʳǤϾͤβǽϾʤŹŪ˰ʥϥåؿΤޤȤȥϥåͤ뤿λ֤äƤޤ⤷ʤ
ԤΥץϡԥ塼ʳؤˤƤǤˤĤˡƤƤ롣㤨Хץɥ쥹ˡˡʤɤ롣
Ĥޤǥϥåͤ1äƤΤץɥ쥹ˡǤ롣
ƥϥåǼѤߤʤС˺ƥϥå夷Ƥơƥϥå夷礭Ķʤ顢ƬH(1)롣ʾΤȤޤȤȺƥϥåؿϼΤ褦ˤʤ롣
ץɥ쥹ˡǤϡƤȤ˥Υ˥쥳ɤǼΤǡϥåɽˤ˳ǡ¸ߤƤƤ⡢ϥåͤΰ֤˥ǡȤϸ¤ʤϥåͤΰ֤ˤǡפʤϡƥϥåͤᡢӤƤʤФʤʤϥåͤΰ֤鲼ظƤֲˤä־夫Ĵ٤ƤȤˤʤ롣ϥåɽǤˤ٤ƳǼѤߤξϥϥåɽΥǡ٤Ĵ٤Ƥʤȡǡ¸ߤʤȤ狼롣
̾ΰˤ-1åȤƤ뤳Ȥǡ٤ƤΥǡåʤƤǡʤȤ狼뤳Ȥ롣
㡧329H(1)ޤĴ٤Сϥåɽ¸ߤʤȤ狼롣
ϥåɽ礭Υ˥बäȯʤϥåؿʤСץɥ쥹ˡǤ褤Υ˥ȯͽ¬ǤȤϡ¾ˡѤۤ褤
餫Υ˥쥳ɤΰͽƤإݥĤʤΤˡǤ롣ۥƥ㤨ʤСС֥åȯͽ¬ǤȤͽ˰ޤǶΤޤޥפƤСΤȤˤȤȤ櫓Ǥ롣Υץϼºݤ˥ۥƥαѤˤƤ褯ȤƤ롣
㡧ϥåؿǡmod 5ǷƤ1û褦ʴؿȤ롣ޤH(1)H(5)ޤǤۡ쥳ɤΰ衢H(6)H(10)ޤǤΥ˥쥳ɤΰˤ롣
P(1)6ʤΤǡH(6)˥Υ˥쥳ɤǼƤ뤳Ȥ̣롣ݥ0ΤȤϡΥ˥쥳ɤʤȤ̣롣
ˡ400ǼȤȤͤƤߤ褦ϥåͤ1H(1)ϤǤ˳ǼѤߤʤΤǡƤH(7)˳Ǽ롣ơH(1)ݥɤäơP(6)Υݥ7ˤΤǤ롣
ΥץνפʥݥȤϡϥåɽ˥ݥĤȤǤ롣嵭ǤϥݥѤPѤƤ뤬2ˤƼ륿פ⤢롣
ƵΤ褦롣
ϥåͤΥǡȰפʤȤƥϥåͤɬפꡢήޤϥ롼¤ˤʤ롣롼פνλϼ̤Ǥ롣
λ郎ʣʤΤǡ˼ήޤǤϡflgȤѿѤ롣ήޤέϡ嵭ֹб롣
nP(n)פǡݥФƤΤݥȤǤ롣
ϥåˡˤõǤϡΥ˥बȯʤ硢Ǥο˴طʤϥåؿη1¹Ԥ롣Ĥޤꡢϥåˡη̤ΥǤ롣
ϥåˡˤäơñϿJavaץäƤߤ롣Τ褦ʵǽ롣
ñϿȸϥ饹åɤˤ롣ϿInsertåɡSearchåɤȤ롣
InsertåɤϡmainåɤϿñ롣
1 2 3 4 5 6 |
|
Ǥϥ르ꥺInsert(string)ˤĤƲ⤹롣
1ܤstringΥϥåͤơhƤ롣
2ܤܤΥϥå쥳ɤʸĹ0ǤʤʤС0֤ǤʤʤСϤǤstringhܤΥ쥳ɤɲäơ1֤
Searchåɤϡmainåɤ鸡ñ롣
1 2 3 4 |
|
Ǥϥ르ꥺSearch(string)ˤĤƲ⤹롣
1ܤstringΥϥåͤơhƤ롣
2ܤhܤΥϥå쥳ɤʸפƤ뤫Ĵ٤롣JavaǤString饹equalåɤȤäơif(HashTable[h].equals(s) == true){}פȤФ褤פƤʤСֹh֤
mainåɤǤϡ2ĤΥåɤȤäΤ褦ʽˤʤ롣
Ǹ˹ͤʤФʤʤΤȤơϥåؿ롣ŹǻȤϥåؿǤϤʤǤϼΤ褦ñʻȤߤδؿѤ뤳Ȥˤ롣
1 2 3 4 5 |
|
ϥåˡ¹ԤJavaΥץϼ̤ǤHashTest.javaˡ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
| - | | | | | | | | - | | - | ! | | | | ! | | | | - | - | ! | | ! | | | | - | - | ! | ! | | - | - | | - | - | | ! | | | - | ! | | | - - | | | | - | ! | | - | | | | ! - | | ! ! | | | - | | ! | | | - | - | | | | - | ! | | | | - | | - | | ! - | | ! ! ! ! |
|
Υץ¹ԤȡΤ褦ˤʤ롣ϥåơ֥ǿǿˤȳڤ뤳ȤʤʤΤǡϥåͤʬ褦ˤʤ롣äơǤϰȤ11ꤷ
> java HashTest 11 ο11ˤ 0: ñʽλˡ Ͽ⡼ɤϤޤ롣 test testHashTableϿ롣 Hash:448 testΥϥåͤ448Ǥ롣 ->8 448 (mod 11)8פȷǤΤǡ8testϿ 1: ñʽλˡ hack Hash:407 ->0 2: ñʽλˡ crack Hash:516 ->10 3: ñʽλˡ krack Hash:524 ->7 4: ñʽλˡ virus Hash:569 ->8 ͤȯ virus8ϤǤñ줬ʾͤˡ 4: ñʽλˡ network Hash:778 ->8 ͤȯ network8ϤǤñ줬ʾͤˡ 4: ñʽλˡ ϤơϿ⡼ɤϽλ 0:hack HashTableɽơ⡼ɤ˰ܹԤ롣 7:krack 8:test 10:crack õñʽλˡ hack Hash:407 ->0 hack0ܤǤ롣 õñʽλˡ crack Hash:516 ->10 crack10ܤǤ롣 õñʽλˡ network networkHashTable¸ߤʤϿΤȤ˾ͤ顢ɲäʤä Hash:778 ->8 networkϸĤʤ õñʽλˡ Ϥơ⡼ɤϽλ
ͤǤѤʥץǤ륪ץɥ쥹ˡͤƤߤ롣ϥåͤ1ơǿdzä;ȤˡǤ롣ΰ֤Ǥͤ顢1;롣Ƥ֤ĤޤǷ֤ΤǤ롣
ҤInsert르ꥺSearch르ꥺФ褤
1 2 3 4 5 6 7 |
|
嵭ץTestHash.javaˤˤƤϡ(ǿ)TableMax˳롣ޤHashåɤѤ餺ΤޤȤäƤ褤
1 2 3 4 5 6 |
|
Ƽõ르ꥺΥޤȤƤ
르ꥺ̾ | |
ϥåˡ | |
õˡ | |
Хʥꥵ |
1ֿؿnпؿlog(n)ĿǤ롣