Временная сложность кода ниже

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");

Answer 2

Похоже, вы пытаетесь закодировать строку.В таком случае вы можете использовать метод UrlPathEncode ().Если вы пытаетесь только кодировать пробелы, используйте Replace () (как упомянуто Дугласом).