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