1

私のコードが O(N) 時間 (線形時間?) または O(N^2) 時間またはその他の時間で実行されるかどうかをどのように判断しますか? 演習では、計算に時間がかかるコードのオンライン ドック ポイントをテストします。

実行にかかる時間が入力データの長さにのみ比例するスクリプト ( O(N) time ) を用意するのが最善であることを理解しています。また、コードの実行速度をどのように判断できますか?

以下に、私が書いた、私が懸念しているスクリプトを含めます。これは、一連の「a」と「b」が与えられ、回文を計算する模擬試験の問題からのものです。したがって、s = "baababa" が与えられた場合、6 つの回文があります: 'aa'、'baab'、'aba'、'bab'、'ababa'、および 'aba' です。

def palindrome(s):
  length = len(s)
  last = len(s)-1
  count = 0

  for index, i in enumerate(s):
    left=1
    right=1
    left2=1
    right2=1

    for j in range(0,index+1): #+1 because exclusive
      if index-left2+1>=0 and index+right2<=last and s[index-left2+1]==s[index+right2]:
        print s[index-left2+1:index+right2+1] #+1 because exclusive
        left2 +=1
        right2 +=1
        count +=1

      elif index-left>=0 and index+right<=last and s[index-left] == s[index+right]:
        print s[index-left:index+right+1] #+1 because exclusive
        left += 1
        right +=1
        count += 1

  return count

これは O(N) 時間ですか? リスト全体を1回だけループしますが、小さなループもあります...

4

3 に答える 3

3

O(N^2)です。0 から N までの 1 つのループと、0 から i までの 2 番目のループがあります。実行する必要がある操作の量を見てみましょう。各 'i' について、j のリストのサイズを 0 から i + 1 まで調べます (N = 7 とします)。

i = 0 | x x _ _ _ _ _ _  -
i = 1 | x x x _ _ _ _ _  |
i = 2 | x x x x _ _ _ _  |
i = 3 | x x x x x _ _ _  N
i = 4 | x x x x x x _ _  |
i = 5 | x x x x x x x _  |
i = 6 | x x x x x x x x  _
       |-----N + 1-----|

長方形全体の面積は ~ N * N (実際には N * (N + 1) ですが、ここではそれほど重要ではありません) であるため、 ~ N ^ 2 / 2 回の操作があることがわかります。そしてそれはO(N^2)です。

于 2013-07-21T18:49:36.713 に答える
3

さて、これを考えてみましょう。入力のサイズは ですn = len(s)。文字ごとに、0 からインデックスまでループします。したがって、次を取得できます

for i = 0 to n
    for j = 0 to i + 1
        1

これはに減らすことができます

for i = 0 to n
    (i + 1)(i + 2)

それから私たちに

for i = 0 to n
    i^2 + 3i + 2

3i + 2次に、これを分割して削減できます。O(n^2) であるため、3(n)(n + 1) + 2n = 3n^2 + 5nすぐに線形ではないことがわかり ます。また、2番目のforループを使用して何をしているのかわかりません。最後の文字と最初の文字を比較することで、回文を線形時間で計算できます。

方法を知りたい場合: http://rosettacode.org/wiki/Palindrome_detection#Python

于 2013-07-21T18:50:05.713 に答える
1

これは O(N) 時間ではありません。enumerate(s)配列を一度だけループしますが。ループごとに、追加の作業を行います。配列の長さが N であると仮定します。したがって、繰り返しの総数は約 1+2+3+..+N になり、これは N*(N+1)/2 であり、O(N に単純化されます。 ^2) 実行時間。

于 2013-07-21T18:53:18.913 に答える