8

私は最近、2 つの文字列が互いにアナグラムであるかどうかをチェックするアルゴリズムの設計を依頼されました。私の目標は、空間と時間の複雑さを最小限に抑えることだったので、次のアルゴリズムを思いつきました。

  1. それぞれゼロに初期化された 26 要素の配列を作成します。
  2. 最初の文字列をトラバースし、文字ごとに、その文字に対応する配列要素をインクリメントします。
  3. 2 番目の文字列をトラバースし、文字ごとに、その文字に対応する配列要素をデクリメントします。
  4. アレイ全体をスキャンします。すべての要素が 0 の場合、2 つの文字列はアナグラムです。

ただし、このアルゴリズムの時間の複雑さは O(n) であり、より複雑なアルゴリズムを思いつくことはできません。誰か知っていますか？

4

5 に答える 5

15

あなたのアルゴリズムは漸近的に最適です。この問題を Ω(n) 時間以上で解くことは不可能です。これを確認するために、問題を o(n) 時間で解決できるアルゴリズム A が存在すると仮定します (ここでは n の小さな o であることに注意してください)。次に、任意の 1 > ε > 0 に対して、少なくとも n サイズの任意の入力に対して、アルゴリズムが最大 εn ステップで終了しなければならない n がいくつかあります。ε = 1/3 を設定し、この ε の前述の n に対して長さが少なくとも n であるアルゴリズムへの入力を検討します。アルゴリズムは 2 つの文字列の最大 1/3 の文字を調べることができるため、関数には 2 つの異なる入力が必要です。1 つはアナグラムのペアであり、もう 1 つはそうではありません。各入力の文字の同じサブセット。その場合、関数はそれぞれの場合で同じ出力を生成する必要があります。したがって、入力の少なくとも 1 つは間違っています。矛盾に達したので、そのようなアルゴリズムは存在しないはずです。

于 2011-03-29T09:02:35.213 に答える
3

早期終了により、平均パフォーマンスを改善できる可能性があります。2 番目の文字列をスキャンしているときに、デクリメントする前に count[char] が 0 の場合、アナグラムがなく、スキャンを停止できます。

また、文字列が 26 文字よりも短い場合は、最後の手順で、最初の文字列の文字のみでゼロをチェックします。

これは大きな O を変更しませんが、データによっては、平均ランタイムを提案されたソリューションの 2N+26 未満に変更できます。

于 2011-08-20T23:47:15.830 に答える
1

文字列がアナグラムであることを確認するには、文字列全体を比較する必要があります。

于 2011-03-29T09:00:13.437 に答える
-2 
int anagram (char a[], char b[]) {

  char chars[26];
  int ana = 0;
  int i =0;

  for (i=0; i<26;i++)
        chars[i] = 0;


  if (strlen(a) != strlen(b))
        return -1;

  i = 0;
  while ((a[i] != '\0') || (b[i] != '\0')) {
        chars[a[i] - 'a']++;
        chars[b[i] - 'a']--;
        i++;
  }

  for (i=0; i<26;i++)
        ana += chars[i];

   return ana;

}


void main() {

  char *a = "chimmy\0";
  char *b = "yimmch\0";

  printf ("Anagram result is %d.\n", anagram(a,b));


}
于 2013-04-23T18:17:43.527 に答える