C++の文字列とchar配列の宣言の時間の複雑さの違いは何ですか？

Question

linkという質問では、まず文字配列を使って試しました。この解決策は期限を超えました。

char s[100000]; 
    cin >> s; 
    int cnt[26]; 
    for(int i=0;i<26;++i) 
     cnt[i]=0; 
    for(int i=0;i<strlen(s);++i) 
     cnt[s[i]-'a']++; 
    int count =0; 
    for(int i=0;i<26;++i) 
     if(cnt[i]>0) 
      count++; 
    cout << count << endl; 

しかし、私はこれに上記のコードを変更：

string s; 
    cin >> s; 
    int cnt[26]; 
    for(int i=0;i<26;++i) 
     cnt[i]=0; 
    for(int i=0;i<s.length();++i) 
     cnt[s.at(i)-'a']++; 
    int count =0; 
    for(int i=0;i<26;++i) 
     if(cnt[i]>0) 
      count++; 
    cout << count << endl; 

そして簡単に渡されたコード。また、最初のものは1秒の制限時間を超え、2回目は0.04秒の実行時間を過ぎた。なぜそのような実行時間に大きな違いがありますか？

Answer 1

Cの文字列は、長さを明示的に格納しません。末尾にはnullがあります。長さを調べるには、文字列ごとに文字列全体を反復処理する必要があります。 'sid :: string :: length'は内部的に格納されている長さを返します。

ループの前に変数の長さをキャッシュし、forステートメントでキャッシュされた長さを使用することで、Cバージョンのスピードアップを簡単に行うことができます。

Answer 2

std::stringは、その長さを別々に格納するので、s.size()は即座の操作です。

for(int i=0;i<strlen(s);++i)は、繰り返しごとにstrlen(s)を呼び出し、strlenは、文字列の長さを見つけるために文字列全体を最後までループします。ですから、この無邪気なループは実際にはO（n ）の複雑さです。