下面代码的时间复杂度

Question

我正在尝试检查以下简单程序的时间复杂度.该程序用字符串替换字符串中的空格'%20'.

1. 计算空格的循环(O(1)时间)

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

2. 替换空格的循环(O(n),其中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

计算空间的循环O(n)不需要O(1),因为你正在迭代 - 并执行检查 - n字符串中的每个字符.

如你所说,更换循环需要O(n).O(n)顺序执行的两个操作具有组合的复杂度O(n)(以Big-O表示法丢弃常数因子).

PS你知道你可以使用一行来实现所有代码的等效吗？

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