아래 코드의 시간 복잡도

Question

아래의 간단한 프로그램의 시간 복잡성을 확인하려고합니다. 문자열의 공백을 '%20'으로 바꿉니다.

1. 루프는 공간 (O (1) 시간)

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

2. 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++; 
        } 
       } 
   

(N은 스트링의 크기가 O (N))의 공간을 대체하기 위해 루프를 세는

그래서 "O (n) + O (1)"해결책이라고 추측합니다. 내가 틀렸다면 나를 바로 잡아주세요.

Answer 1

문자열의 n자를 반복 반복하고 검사를 수행하므로 루프를 계산하는 루프는 O(n)이 아니라 O(1)이됩니다.

앞에서 말씀 드린대로 대체 루프는 O(n)이됩니다. 순차적으로 수행되는 두 개의 O(n) 연산은 O(n)의 결합 된 복잡성을가집니다 (상수 인수는 Big-O 표기법에서 무시됩니다).

P. 한 줄로 모든 코드를 처리 할 수 ​​있다는 것을 알고 계십니까?

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

Answer 2

문자열을 인코딩하려는 것처럼 보입니다. 이 경우 UrlPathEncode() 메소드를 사용할 수 있습니다. 공백 만 인코딩하려는 경우 Replace()를 사용합니다 (Douglas에서 언급 한대로).