以下のコードの時間複雑度

Question

私は以下の簡単なプログラムの時間複雑さをチェックしようとしています。 プログラムは、文字列内のスペースを'%20'に置き換えます。

1. スペース（O（1）時間）

   foreach (char k in s) 
       { 
        if (k == ' ') 
        { 
         spaces_cnt++; 
        } 
       } 
   

2. を（nは文字列のサイズであり、O（n））をスペースを交換するループをカウントするループ

   char[] c = new char[s.Length + spaces_cnt * 3]; 
       int i = 0; 
       int j = 0; 
       while (i<s.Length) 
       { 
        if (s[i] != ' ') 
        { 
         c[j] = s[i]; 
         j++; 
         i++; 
        } 
        else 
        { 
   
         c[j] = '%'; 
         c[j + 1] = '2'; 
         c[j + 2] = '0'; 
         j = j + 3; 
         i++; 
        } 
       } 
   

私はそれが "O（n）+ O（1）"解決策であると推測しています。私が間違っていれば私を修正してください。

Answer 1

文字列内の各n文字を繰り返し処理して確認しているので、ループをカウントするループはO(n)ではなく、O(1)になります。

あなたが述べたように、置換ループはO(n)になります。シーケンシャルに実行される2つの操作は、O(n)（複雑な定数はBig-O表記法では破棄されます）の複合複雑さを持ちます。

P.S. 1行ですべてのコードと同等の効果を得ることができますか？

s = s.Replace(" ", "%20"); 

Answer 2

文字列をエンコードしようとしているようです。そのような場合は、UrlPathEncode（）メソッドを使用できます。スペースをエンコードするだけの場合は、Replace（）を使用します（ダグラスの言葉通り）。