c# - 下面代码的时间复杂度

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 表示法中丢弃常数因子)。

附言您知道您可以使用一行实现所有代码的等价物吗？

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