2

この質問について助けが必要です。時間計算量は O(n) だと思いますが、私の友人はこれが O(n^2) だと主張しています。理由の1つはfn = fn[index+1 ::] 

#filename: string_expression_matcher.cc
#string: stxpm.c
#should return



import sys
string = "string_expression_matcher.cc"
subStr = "stxpm.c"

fn = list(string)
for i in subStr:
    try:
        index = fn.index(i)
        fn = fn[index+1 ::]
    except:
        print ("can't dup")
        sys.exit()

print ("found")

これが私のアルゴリズムです：

  1. subStr の s:
    • ループは「string_expression_matcher.cc」から始まります。
    • このステップの残りの文字列出力は「tring_expression_matcher.cc」です。
  2. subStr の t
    • ループは「tring_expression_matcher.cc」から始まります。
    • 残りは「ring_expression_matcher.cc」です。
  3. x in subStr
    • ループは「ring_expression_matcher.cc」から始まります。
    • 残りは「pression_matcher.cc」
  4. p in subStr
    • ループは「pression_matcher.cc」から始まります。
    • 残りは「resion_matcher.cc」です。

最後のステップまで続きます。

与えられた:

n = len(subStr)
m = len(string)`

このプログラムの時間計算量は? みんなありがとう、でも私は本当にO(n)かO(n^2)か知りたい。コードが完璧ではないことはわかっていますが、時間の複雑さに注意してください..どうもありがとう

Python文字列コピーの仕組みを知っている人はいますか? fn = fn[index+1 ::] を実行するとどうなりますか?

特級エンジニアに聞いてみました。彼は、結果は O(m*n) であると言いました。君はどうでしょう？

4

3 に答える 3

1

あなたのアルゴリズムは（比較の数に関して）O(n)、nは文字列の長さです。最悪の場合、文字列とパターンの両方が同じになり、すべての文字がsubStrの次の文字に移動しますstring。文字列の単純な比較と同等です。

ただし、実装はO(n^2)他の操作に関するものである可能性があり、その理由は、質問で述べたように、次の行です。

fn = fn[index+1 ::]

これは実質的に文字列をコピーしています (上記のスライスがコピーとして実装されていると仮定します)。前の例をもう一度考えると、文字列内のすべての文字について、残りのすべての文字をコピーする必要がありますO(n^2)。これは、n-1最初に文字をコピーし、次にn-2、n-3というようにコピーし、最後の反復で 1 文字だけをコピーするためです。コピーされるアイテムの合計量はn-1+ n-2+ ...+1となり、これは等差数列としてに等しくなり(n-1)*((n-1)+1)/2 = (n-1)*n/2 = O(n^2)ます。他の状況では、これは に一般化できます。O(m*n)ここでm、 はパターンの長さです。

あなたの友人があなたに言いたいことは、あなたのアルゴリズムは線形ですが、あなたの実装はそうではありません. でも簡単に解決できます。@thkang によって提示されたソリューションまたはより透過的なものを使用して、隠れた複雑さを取り除きます。次に例を示します。

try:
  si = iter(string)
  for c in subStr:
    while c != si.next():
      pass
except StopIteration:
  print "no match"
else:
  print "match"
于 2013-03-27T19:17:02.247 に答える
1

申し訳ありませんが、これは O(n) でも O(n+m) でもありません。どちらも O(n^2) より優れており、このアルゴリズムは O(n^2) です。なんで？

  1. O(n) の複雑さを持つソース文字列を反復処理します
  2. 各反復で、O(n) の複雑さを持つ文字列で「インデックス」を呼び出します

したがって、これは最悪の場合のパフォーマンスが O(n^2) で制限されており、実際には単純な検索アルゴリズムの実装です。O(n)/O(mn) を見たい場合は、Boyer-Moore アルゴリズムをチェックすることをお勧めします

于 2013-04-18T10:26:25.767 に答える
0

リスト全体をコピーしたくない場合は.index、開始インデックスを指定して使用します。

last_index = 0
for i in subStr:
    try:
        last_index = fn.index(i, last_index) + 1
    except ValueError:
        print ("can't dup")
        sys.exit()
else:
    #string matches
于 2013-03-27T18:32:51.573 に答える