質問編集履歴
1
プログラムの詳細記述、私の考えた答えを記述しました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,33 +1,81 @@
|
|
|
1
|
-
Rubyのプログラムにおける計算量を求めたいのです
|
|
1
|
+
Rubyのプログラムにおける計算量を求めたいのです。
|
|
2
2
|
|
|
3
|
-
|
|
3
|
+
|
|
4
4
|
|
|
5
5
|
https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c
|
|
6
6
|
|
|
7
7
|
このページを見ると、
|
|
8
8
|
|
|
9
|
-
計算量
|
|
9
|
+
計算量を論理的に求められると書いてあるので、以下の通りにしました。(言語はRuby)
|
|
10
10
|
|
|
11
|
-
|
|
11
|
+
ユーザー入力を回文かどうか判定するプログラムです。
|
|
12
|
-
|
|
13
|
-
|
|
14
12
|
|
|
15
13
|
```ruby
|
|
16
14
|
|
|
17
|
-
#
|
|
15
|
+
#ユーザー入力
|
|
18
16
|
|
|
19
|
-
s
|
|
17
|
+
puts "回文か判定しますので、文字を入力してください"
|
|
20
18
|
|
|
21
|
-
|
|
19
|
+
answer=gets.chomp
|
|
22
20
|
|
|
23
|
-
|
|
21
|
+
#クラス定義、回文判定メソッド定義、処理時間計測開始
|
|
24
22
|
|
|
25
|
-
|
|
23
|
+
class Word
|
|
26
24
|
|
|
25
|
+
def checkPalindrome(word)
|
|
26
|
+
|
|
27
|
+
word = word.to_s
|
|
28
|
+
|
|
29
|
+
size = word.length / 2
|
|
30
|
+
|
|
31
|
+
return ( word[0..size] == word.reverse[0..size] )
|
|
32
|
+
|
|
33
|
+
end
|
|
34
|
+
|
|
35
|
+
end
|
|
36
|
+
|
|
37
|
+
if Word.new.checkPalindrome(answer)
|
|
38
|
+
|
|
39
|
+
puts "それは回文です"
|
|
40
|
+
|
|
27
|
-
|
|
41
|
+
else
|
|
42
|
+
|
|
43
|
+
puts "それは回文ではありません"
|
|
44
|
+
|
|
45
|
+
end
|
|
46
|
+
|
|
47
|
+
|
|
28
48
|
|
|
29
49
|
|
|
30
50
|
|
|
31
51
|
```
|
|
32
52
|
|
|
53
|
+
** 私は以下の通り考えました。**
|
|
54
|
+
|
|
55
|
+
|
|
56
|
+
|
|
57
|
+
n=ユーザー入力の文字数
|
|
58
|
+
|
|
59
|
+
とすると、
|
|
60
|
+
|
|
61
|
+
比較する文字数は
|
|
62
|
+
|
|
63
|
+
n/2
|
|
64
|
+
|
|
65
|
+
となります。（８文字だったら、前からの４文字と後ろからの４文字を順番に比べていく為。）
|
|
66
|
+
|
|
67
|
+
つまり、計算量（文字を比較する回数）は
|
|
68
|
+
|
|
69
|
+
O(n/2)
|
|
70
|
+
|
|
71
|
+
となり、係数は無視されるので、計算量は
|
|
72
|
+
|
|
73
|
+
O(n)
|
|
74
|
+
|
|
75
|
+
となります。
|
|
76
|
+
|
|
77
|
+
間違っていたらご教示ください。
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
33
|
-
|
|
81
|
+
以前は私の理解不足だけでなく、丸投げな回答をしてしまい、申し訳ございませんでした。
|