2つの文字列が互いの順列であるかどうかを判断するプログラムの時間複雑度

Question

2つの文字列が互いの順列であるかどうかを判断するプログラムを作成しました。私はハッシュテーブルを使ってそうしようとしています。ここに私のコードです：

bool permutation(string word1, string word2) { 

    unordered_map<char, int> myMap1; 
    unordered_map<char, int> myMap2; 
    int count1 = 0; 
    int count2 = 0; 

    if (word1.length() == word2.length()) { 
     for (int i = 0; i < word1.length(); i++) { 
      count1++; 
      count2++; 
      for (int j = 0; j < word1.length(); j++) { 
       if (word1[i] == word1[j] && myMap1.find(word1[i]) == myMap1.end()) { 
        count1++; 
       } 
       if (word2[i] == word2[j] && myMap2.find(word1[i]) == myMap2.end()) { 
        count2++; 
       } 
      } 
      myMap1.insert({word1[i], count1}); 
      myMap2.insert({word2[i], count2}); 
     } 
    } 
    else { 
     return false; 
    } 
    return (myMap1.size() == myMap2.size()); 
} 

int main() { 

    string word1; 
    string word2; 
    getline(cin, word1); 
    getline(cin, word2); 

    bool result = permutation(word1, word2); 

    return 0; 
} 

私は上記のコードの時間の複雑さはO（n^2）だと思います。ネストされたループの使用を伴わないアルゴリズムは考えられませんでした。ハッシュテーブルを使ってこれを行うより速い方法がありますか？

Answer 1

イエップ。

#include <climits> 
#include <iostream> 
#include <unordered_map> 

namespace { 

bool permutation(const std::string& word1, const std::string& word2) { 
    std::unordered_map<char, std::size_t> freqdiff; 
    // alternatively, std::size_t freqdiff[UCHAR_MAX + 1] = {}; 
    for (char c : word1) { 
    // alternatively, freqdiff[(unsigned char)c]++; 
    freqdiff[c]++; 
    } 
    for (char c : word2) { 
    // alternatively, freqdiff[(unsigned char)c]--; 
    freqdiff[c]--; 
    } 
    for (auto i : freqdiff) { 
    // alternatively, i != 0 
    if (i.second != 0) { 
     return false; 
    } 
    } 
    return true; 
} 

bool permutation_with_array(const std::string& word1, 
          const std::string& word2) { 
    std::size_t freqdiff[UCHAR_MAX + 1] = {}; 
    for (char c : word1) { 
    freqdiff[static_cast<unsigned char>(c)]++; 
    } 
    for (char c : word2) { 
    freqdiff[static_cast<unsigned char>(c)]--; 
    } 
    for (std::size_t i : freqdiff) { 
    if (i != 0) { 
     return false; 
    } 
    } 
    return true; 
} 
} 

int main() { 
    std::string word1; 
    std::string word2; 
    std::getline(std::cin, word1); 
    std::getline(std::cin, word2); 
    std::cout << permutation(word1, word2) << '\n'; 
    std::cout << permutation_with_array(word1, word2) << '\n'; 
} 

Answer 2

TL; DRは、私は（私自身を含む）のソリューションをテストしたかった：Davidのマップベースの答えがされた、彼のアレイベースのソリューションは非常によく実行し、（それは多くの一般的なもので）ちゃんとうまく行って自分のソリューションわずかに速いだけでなく、やや読みにくい（おそらく価値がない）かもしれない。

私はこれを見て、無秩序な地図のDavidの答えがおそらく最も時間の複雑さが少ないと信じられませんでした。

私はたいていC言語で書いているので、C++がこれらのデータ構造でどのような最適化を提供しているのか、あるいは実際にどれだけうまくいくのかはわかりません。だから私はそれをテストすることにしました。

だから私は2つの順列及び2）2異なる）若干の改造（source code here）

で、私は1上のプログラムに100000回走った、様々なソリューションのパフォーマンスをテストするために、私のi7の上でいくつかのテストを設定

PERM original 
====================== 
PERMUTATIONS OF SAME WORD 
real 104.73 
user 104.61 
sys 0.06 

DIFFERENT WORDS 
real 104.24 
user 104.16 
sys 0.02 

PERM David map 
====================== 
PERMUTATIONS OF SAME WORD 
real 2.46 
user 2.44 
sys 0.00 

DIFFERENT WORDS 
real 2.45 
user 2.42 
sys 0.02 

PERM David array 
====================== 
PERMUTATIONS OF SAME WORD 
real 0.15 
user 0.14 
sys 0.00 

DIFFERENT WORDS 
real 0.14 
user 0.14 
sys 0.00 

PERM Me 
====================== 
PERMUTATIONS OF SAME WORD 
real 0.13 
user 0.13 
sys 0.00 

DIFFERENT WORDS 
real 0.14 
user 0.12 
sys 0.01