3

私はダブルメタフォンアルゴリズムを見ています。アルゴリズムが該当する効率クラスを計算したいだけです。これはPythonです。これは私が見つけた中で最も読みやすいコードです。

私はアルゴリズムの分析に長けていませんが、このアルゴリズムのwhileループに最も時間がかかることはわかっています。この場合、プログラムは文字列内の各文字を左から右に調べます。

while pos <= last :

これにはnステップかかると思います。ここで、nは文字列の長さです。

ただし、アルゴリズムには、このループ内に多数の「if」および「elif」ステートメントがあります。それらが時間に大きな影響を与えるかどうかはわかりません。誰かが私にこれをステップスルーできますか？合計で時間効率を計算したいと思います。

私自身の質問に答えようとすると、最も効率的なのは長さ1の文字列であり、「if」ステートメントをできるだけ少なく入力する必要があると思います。一方、最悪のシナリオは、おそらく非常に長い文字列です。

ありがとうございました！

4

1 に答える 1

3

すべての条件を見なくても、これは私には直線的に見えます。以下のいくつかの例外を除いた単純なルールは、if / thenステートメントは、何らかのループまたは再帰を行わない限り、アルゴリズムの漸近ランタイムに影響を与えないということです。私が見たものはすべて、一定時間の操作のように見えます。

本当に確認する必要がある場合は、次のようにアプローチします。条件ステートメントに直接依存していない場合は、いくつかのことを探す必要があります

  1. break制御の流れを変えるステートメントやその他のもの-これは漸近時間を短縮する可能性があります
  2. whileorステートメントの変数が不規則に変更されるとfor、アルゴリズムに時間がかかる可能性があります。ここで、これはどちらposかを意味するか、last変更されます。

これは包括的なリストではありませんが、役立つ場合があります。

于 2012-04-28T23:02:55.153 に答える