Является ли временная сложность этого кода O (N^2)

Question

Это мое решение для одной из проблем в leetcode. Через мои выводы я сделал вывод, что он имеет общую сложность времени O (N^2). Тем не менее, я хотел бы получить подтверждение об этом только для того, чтобы не продолжать делать те же ошибки, когда речь заходит о суждении сложности времени и пространства алгоритма.

О, и проблема состоит в следующем:

Учитывая входной строки, обратный строку слово за словом. , например. "Я тебя" == "ты я"

Код выглядит следующим образом: -

public String reverseWords(String s) { 
     //This solution is in assumption that I am restricted to a one-pass algorithm. 
     //This can also be done through a two-pass algorithm -- i.e. split the string and etc. 

     if(null == s) 
      return ""; 
     //remove leading and trailing spaces 
     s = s.trim(); 
     int lengthOfString = s.length(); 
     StringBuilder sb = new StringBuilder(); 
     //Keeps track of the number of characters that have passed. 
     int passedChars = 0; 
     int i = lengthOfString-1; 
     for(; i >= 0; i--){ 
      if(s.charAt(i) == ' '){ 
       //Appends the startOfWord and endOfWord according to passedChars. 
       sb.append(s.substring(i+1, (i+1+passedChars))).append(" "); 
       //Ignore additional space chars. 
       while(s.charAt(i-1) == ' '){ 
        i--; 
       } 
       passedChars = 0; 
      }else{ 
       passedChars++; 
      } 
     } 

     //Handle last reversed word that have been left out. 
     sb.append(s.substring(i+1, (i+1+passedChars))); 

     //return reversedString; 
     return sb.toString(); 
    } 

Мои рассуждения для этого будучи O (^ 2 N) алгоритм: -

1. цикл = о (п)
2. StringBuilder.append = O (1) метод
3. подстроку = о (п) [от Java 7]

На этом примечании, если у кого-либо есть лучшее решение, чем это, вы можете поделиться им! :)

Я стремился к однопроходному решению и, следовательно, отказался от разделения строки перед циклом.

Цените помощь!

EDIT: Я хотел спросить о временной сложности части кода, содержащей цикл. Я заранее извиняюсь, если этот вопрос вводит в заблуждение/запутывает. Весь фрагмент кода предназначен для разъяснения. :)

Answer 1

Сложность времени O(n). (append(x)) StringBuilderO(|x|), где | - размер добавляемой строки ввода. (независимо от состояния застройщика, в среднем).

Ваш алгоритм выполняет итерацию всей строки и использует String#substring() для каждого слова в ней. Поскольку слова не пересекаются, это означает, что вы делаете substring() для каждого слова один раз и добавляете его к строителю (также один раз) - давая вам 2|x| для каждого слова x.

Подводя итог, дает

T(S) = |S| + sum{2|x| for each word x} 

Но так как sum{|x| for each word x} <= |S|, это дает в общей сложности:

T(S) = |S| + 2sum{|x| for each word x} = |S| + 2|S| = 3|S| 

С | S | является размер входа (n), это O(n)

---

Обратите внимание, что важная часть находится в jdk7, метод substring() является линейным размером выходной строки, не оригинал (копировать только соответствующая часть, а не вся строка).

Answer 2

Это альтернативное решение, которое, скорее всего, будет лучше.

public String reverseWords(String s) { 
    String[] array = s.split(" "); 
    int len = array.length; 

    StringBuilder sb = new StringBuilder(); 
    for (int i = 0; i < len; i++) { 
     sb.append(" ").append(array[len - i - 1]); 
    } 

    return sb.toString().trim(); 
} 

Answer 3

Amit уже дал вам подробное объяснение по вычислению сложности, я хотел бы дать вам более простую версию.

В общем случае, если у нас есть вложенные циклы, мы считаем сложность O (N^2). Но это не всегда так, как вам нужно сделать некоторую активность n раз для каждой n-й части ввода. Например, если у вас есть ввод размера 3, вы должны сделать какое-то действие 3 раза на каждом элементе. Затем вы можете сказать, что ваш алгоритм имеет сложность O (n^2).

Поскольку вы просматриваете и обрабатываете каждую часть строки ввода только один раз (даже если вы используете вложенные циклы), сложность должна быть порядка O (n). Для доказательства Амит проделал большую работу.

Хотя, я бы использовал ниже код, чтобы изменить порядок слов

String delim = " "; 
String [] words = s.split(delim); 
int wordCount = words.length; 

for(int i = 0; i < wordCount/2; i++) { 
    String temp = words[i]; 
    words[i] = words[wordCount - i - 1]; 
    words[wordCount - i - 1] = temp; 
} 

String result = Arrays.toString(words).replace(", ", delim).replaceAll("[\\[\\]]", "");