o (n^3) C++ 코드의 복잡성 감소

Question

다음 알고리즘의 복잡성을 줄이려 고합니다. 기본적으로 단어는 입력으로 사용되며 그 안에있는 고유 한 문자의 수 (단어의 "엔트로피")를 계산합니다. 현재의 솔루션은 3 개의 임베디드 for 루프를 사용하며, 이것은 o (n^3)의 복잡성을 낳습니다. 이 코드는 더 큰 프로젝트 (우리는 boggle로 알려진 게임을위한 솔버를 만들었습니다)의 일부이기 때문에 알고리즘의 복잡성을 줄여 실행 시간을 줄이기를 희망했습니다. 미리 감사드립니다! N (

#include <unordered_set> 

int wordEntropy(const std::string &word) { 
    std::unordered_set<char> uniquechars(word.begin(), word.end()); 
    return uniquechars.size(); 
} 

이것은 O의 복잡성을 산출 :

int wordEntropy(string word) 
{ 

int length = word.length(); 
int uniquewords = length; 
string compare = word; 
char save[17]; 
int cond=0; 

for (int ii=0; ii < length; ii++) 
{ 

    for (int jj=ii+1; jj < length; jj++) 
    { 
     for (int kk=0; kk<= ii; kk++) 
     { 
      if (save[kk] == word[ii]) {cond++;} 
     } 
     if (word[ii] == word[jj]) 
     { 
      if (cond>0) {break;} 
      uniquewords--; 
     } 
    } 

    save[ii] = word[ii]; 
    cond = 0; 

} 
return uniquewords; 
} 

Answer 1

을이 성능에 대해 정말 경우,이 같은 일이 더 빠를 수 있습니다 유효한 문자의 범위에 따라 :

std::size_t wordEntropy(const std::string & word) 
{ 
    unsigned char seen[256] = { 0 }; 
    for(unsigned char c : word) 
    { 
     ++seen[ c ]; 
    } 
    return std::count_if(& seen[0], & seen[ 0 ] + 256, 
          [](unsigned char c) { return c != 0; }); 
} 

분명히 이것은 유지하기가 조금 더 어렵습니다. 이 솔루션은 O (n)의 복잡도가 보장되고 동적 메모리 할당을하지 않습니다. 이 있습니다. 문자는 255 개 이상의 번 발생하면 문제가 발생하지 않는

대체 버전 : 문자열이 짧은 경우

std::size_t wordEntropy(const std::string & word) 
{ 
    bool seen[256] = { false }; 
    for(unsigned char c : word) 
    { 
     seen[ c ] = true; 
    } 
    return std::count_if(& seen[0], & seen[ 0 ] + 256, 
          [](bool t) { return t; }); 
} 

Answer 2

싸게 용액 HashSet의 (상각 O (1)의 삽입 및 조회) 인 unordered_set에 문자를 고집 그냥), 그것은 얻는만큼 좋다.

Answer 3

여분의 (시간이 많이 소요) 메모리 할당하지 않고, 대신 계산을 수행

std::sort(word.begin(), word.end()); 
auto last = std::unique(word.begin(), word.end()); 
return last - word.begin(); 

Answer 4

, 당신은 큰-O보다 메모리 allocs 더 걱정해야한다. 어느 쪽이든, 여기에 더 빠른 해결책이 있습니다.

이 글은 boggle 게임용이며이 함수에 대한 입력은 "word"라는 문자열이라고 언급 했으므로 "word"의 모든 문자가 ascii 알파벳 문자라는 것을 이미 확인했다고 가정합니다. 그렇다면 다음은 아마도 가장 빠른 경우 불변 엔트로피 수입니다.

int word_entropy (std::string const& word) 
{ 
    uint32_t bit_map = 0; 
    for (char const ch : word) 
     bit_map |= static_cast <uint32_t> (1) << (ch & 31); 
    return __builtin_popcount (bit_map); 
}