Q&A
お二方が reverse、== の実装を考慮するとO(n)ではない可能性がある、と言われているのがよくわかりません。reverseも==も脊椎反射レベルのアルゴリズムでO(n)だと思うのです。それより悪い実装を敢えてやるとは思えないので、o(n)ではないとしてもO(n)未満であると思います。お二方は revserse,===の実装がO(n)未満である可能性がある、と言われているのでしょうか？
「回文判定のアルゴリズム」でしたらその可能性も有るかもとは思いますが。
Rubyで回文を判定するプログラムを作成しました。
以下のページを見ると、計算量はO(n)のような関数で表せることがわかります。
https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c
私の作成したこのプログラムは、入力した文字列とその文字列をreverseメソッドによって文字列の順番を逆転させた物を比較して一致するかどうかで回文判定をしています。
つまり文字列の長さに比例して計算量が増えていくので、
入力文字列の長さをnとすると、
計算量＝O（n）
となると思っているのですが、合っていますでしょうか？
皆様のご意見を伺いたいです。
ruby
1#ユーザー入力 2puts "回文か判定しますので、文字を入力してください" 3answer=gets.chomp 4#クラス定義、回文判定メソッド定義、処理時間計測開始 5class Word 6 def checkPalindrome(word) 7 word = word.to_s 8 return ( word == word.reverse ) 9 end 10end 11if Word.new.checkPalindrome(answer) 12 puts "それは回文です" 13else 14 puts "それは回文ではありません" 15end 16
回答5件
0
回文であるかどうかを真面目に判定するとして、
文字列の長さnが偶数の時は、n = 2m より、
str[0] == str[n-1] で、
str[1] == str[n-2] で、……
str[m-1] == str[m]
であるかを調べることになりますかね。（全体の半分を比較すればいい）
同様に文字列の長さnが奇数の場合は、n = 2m+1 から m = (n-1)/2 より、
str[m-1] == str[m+1] までを比較すればいいです。（str[m] は回文にした場合の中心点ですから比較対象が自分自身となります）
どちらにせよ比較のループは最大で m = [n/2] （ただし[] はその中の値を超えない最大の整数）ですから、O(n) です。
※与えられた文字列の後ろ半分を reverse して、ハッシュ値計算……しても変わらないか
多分ですが、よほどへまな実装をしない限り O(n) で判定できるのではないでしょうか。
投稿2019/12/16 07:37
総合スコア13703
0
Rubyで実験してみましたが、word.reverseは文字列長にほぼ比例する時間がかかるようで、O(n)と考えて良いように思います。
投稿2019/12/16 06:32
総合スコア11705
0
ベストアンサー
記述されたコードを素直に読むとO(1)です。
日本語化けてるけど参考までｗ
参照された記事のコメント欄の最初の方を見るとわかりますが、「どのレベルの計算量を求めたいのか？」で変わってくる数字でもあります。
word.reverse の実装まで考慮すると、ちょっと調査がめんどくさい質問になると思います。
投稿2019/12/15 09:38
編集2019/12/15 14:30
退会済みユーザー
総合スコア0
例えば、revserse の実装内で再帰とか発生していると、計算量は大きく変わります。(そういう意味では to_s もですね。)
Ruby は本来回答できる範囲の知識を持ち合わせてないので実装を覗くことはしませんが、コードにあるステップ数以上のモノを追いかけようとするとけっこう大変です。
なので、今回の回答は純粋に記述コードのステップ数のみをカウントしての回答です。
ちなみに、私の脊髄も「revserse は多分O(n)じゃね？」とは言っていますｗ
皆様、本当にありがとうございました。図を使って説明してくださったte2jiさんをベストアンサーにさせていただきました。
私も含まれているようですので返信します。
私が思ったのは、まずreverseが文字数が増えるたびに動的にメモリを確保する可能性です。これでO(n)よりわずかに多い、例えばO(n^1.0001)などになりはしないかと考えています。
==の方は、確定した時点で処理を打ち切れるので、入力によってはn回の繰り返しは必要ありません。ランダムな入力に対してはO(n)でよいのか、例えばO(n^1/2)などになりはしないか、よく分かりません。
あと書いていて思いついたのですが、コンパイルされた結果としてreverseが実際には処理を行わず==側で逆順に処理をするようになるようなことも、まず無いとは思いますが、可能性としては存在しますね。
---
脊椎ではなく脊髄では?
実際にどれだけの計算、時間が必要であるか、と計算量のオーダーであるO(x)とは違うものですから、「文字数が増えるたびに動的にメモリを確保」することを考慮必要なのでしょうか。仮に動的に確保するにしても、そのコストは文字数に比例すると思うので、O(n)ではないかと
「入力によってはn回の繰り返しは必要ありません。」これも、例えばバブルソートはソート済のデータに対してはｎ回で済みますが、O(n^2)として扱われますから、データの質による変化は気にしないのでは（最悪ケースで話すのかなぁ）
「あと書いていて思いついたのですが」これは「回文判定のアルゴリズム」の話で、「回分判定をreverseと==で実装」した場合の話とは異なるかと
実際にかかる時間とオーダーは同じものではありませんが、どんな処理もオーダーに影響しうるので少なくとも考慮は必要だと思います。考慮した上で無視できるならそれでよしです。
コストが文字数に比例するかはあまり考えていなかったので、そうかもしれません。
データの質による変化は気にするべきだと思います。最良ケース・最悪ケース・平均など色々な評価基準があります。
アルゴリズムと実装の話が異なるかは、どうなんでしょうね。プログラマがコードに書いた通りの意図した実装と、コンパイルなど通って実際にコンピュータ上で動く実装は別になりえて、それは考慮すべきかもしれないしそこまで考慮すべきではないかもしれません。
(なおRubyはインタプリタだと思っていたのだが調べるとJITコンパイルもされるらしいので)
> yurugby さん
個人的見解ですが、スクリプト言語では「記述されたコードを素直に読む」以外で計算量を考えるのはあまり意味がないと思っています。
言語に実装されている関数は、実行速度が自前でスクリプトで書くよりも高速であることも多く、また内部で例外処理等の計算量を左右する処理を行っている可能性も否定できません。
バイトコードをちゃんと読めばそれ以上の考慮もできると思いますが、スクリプト言語を使用している価値がなくなります。
そのため、「記述されたコードを素直に読む」かつ
logn, n, nlogn, n^2, n^3, 2^n, n!
ぐらいの粒度で考えて、それ以上の粒度が必要になれば「実測」かなぁとｗ
ここも面白いです。
https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0
> ikadzuchi さん
脊椎は治しますｗ
ちなみに、図はこちらのサイトを使用しました。
https://visualize-ruby.herokuapp.com/
VisualizeRuby ってのがあるようです。
1 文字ずつ確保してコピーしなおしているなら最終的に n 文字コピーするのに (n + 1) * n /2 = (n^2 + n) / 2 文字コピーすることになるので O(n^2) ですね。そんな実装やってるわけないと思いますが。
n 文字分確保して n 文字コピーしているなら O(n) です。
『スクリプト言語では「記述されたコードを素直に読む」以外で計算量を考えるのはあまり意味がないと思っています』というのもわからなくはありませんが、質問の意図を踏まえると組込みのメソッドだから計算量はO(1)だというのは若干違う気がしています。少なくとも簡単に見つかる実装ではO(n)だと思います。https://github.com/ruby/ruby/blob/master/string.c#L5618 単純に文字数分ループで逆順に文字列をコピーしているようです。
この質問は、私の回答がBAに選ばれたことから、リンク先の「計算量の求め方」は正しいのか？という問いだったんだと思います。
で、本回答は「リンク先の考え方でそこそこ良いと思いますよ」というものです。
計算量を「なぜ求めるのか？」が明確でないので目的によっては誤りになりますが、言語の実装を追いかけるのはあまり意味がないと考えています。「少なくとも簡単に見つかる実装ではO(n)だと思います」というぐらいであれば、実測して見るのが適切かと思います。
＊すでに、その方向性で回答されている方もいますね。
ただ、「実装を追いかけると、ホントにO(n)なのか？」というのは個人的に興味深いです。ぜひ、実装を追いかけて解析結果を回答としてまとめてみてください。
0
私の作成したこのプログラムは、入力した文字列とその文字列をreverseメソッドによって文字列の順番を逆転させた物を比較して一致するかどうかで回文判定をしています。
つまり文字列の長さに比例して計算量が増えていくので、
ここの論理が分かりません。
「文字列の長さに比例して計算量が増えていく」は「計算量がO(n)」と同一の意味ですが、
あなたがの質問は
「私のプログラムは文字列の長さに比例して計算量が増えていくが、これは計算量がO(n)か?」でよろしいですか?
それならば定義の問題なので、答えは「はい」です。
ただ、あなたのプログラムが文字列の長さに比例して計算量が増えていくかどうかは、reverseや==の実装に依存しますので私は確信を持って答えられません。
たぶん常識的な長さの範囲においてはほとんどO(n)になるんではないかなあとは思いますが。
投稿2019/12/15 07:18
総合スコア3047
O(x)のｘって １，ｎ、log(n)、n^2、n! とかのオーダーですから、これらの中から選んだら、「nだ」と言ってしまって良いのではないでしょうか
O(n^1.0001)とかってありませんっけ?
そんなのもあるのですか。
そこまで計算量について勉強してきてはいないので知りませんでした。
ないよｗ
少なくともO(n^log_2(3))≒O(n^1.585)はあります。
乗数に出てくる式によってO(n^1.0001)のような値もありうるのではないかと思いますが。
これに意味はあるけど`O(n^log_2(3))`
これに意味はないです`O(n^1.585)`
O(n^1.0001) が存在しうるのは for で n^1.0001 回繰り返すとかだけど、まぁ無い。
だいたい同じ意見のようですね。安心しました。
この回答につけたコメント、なんか誤解を与える表現になっているので、消しはしませんが一旦全て撤回します。
0
合っていると思います。
投稿2019/12/14 08:26
総合スコア23567
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。