Сложность двух вложенных циклов, которые не всегда работают

Question

Мне нужно написать ответ с наименьшей степенью сложности. Мои вопросы касаются вложенных циклов, которые не всегда выполняются. У меня есть цикл for, который выполняет итерацию N раз, в зависимости от длины строки, и ищет значение «char». Когда он находит это, он повторяет цикл снова с этого момента и ищет больше значений «char». Я написал следующий метод:

public static int subStrMaxC(String s, char c, int k) { 
    char[] stringChars=new char[s.length()]; 
    //System.out.print("the string of the characters is"); 
    for(int i=0;i<stringChars.length;i++) { 
     stringChars[i]=s.charAt(i); 
    // System.out.print(stringChars[i]); 
    } 
    int count=0; 
    int bigcount=0; 
    int[] charArray=new int[s.length()]; 
    for(int i=0;i<stringChars.length;i++) { 
      count=0; 
      if(stringChars[i]=='c') { 
       count++; 
       for(int j=i+1;j<stringChars.length;j++) { 
         if(stringChars[j]=='c') { 
          count++; 
          if((count>=2)&&(count<=k+2)) { 
           bigcount++; 
           if(count==k+2) { 
            count=0; 
            j=stringChars.length-1; 
           } 
          } 
         } 
       } 
      } 
    } 
    return bigcount; 
} 

Поскольку второй цикл не итерацию, если первый цикл не находит значение, которое удовлетворяет условию, я не знаю сложность, определена ли O (N^2) -Какой мое предположение, поскольку второй цикл может, в худшем случае, запустить N * (Ni) раз - или просто O (n), что и есть то, что я ищу. Спасибо!

Answer 1

Я уверен, что это лучшее, что вы можете сделать, но, конечно, я могу ошибаться. Проблема с вашим подходом заключается в ограниченном использовании Space Complexity. При подходе ниже вы повторяете строку только один раз (т. Е. Нет цикла j, что приводит к проблеме n квадрата). Здесь вы создаете подстроки кандидата, используя пространство/память. Теперь вам нужно только перебирать подстроки, которые имеют гораздо более низкую временную сложность, чем ваш первый подход.

public class MaxKSubstring { 

public static void main(String[] args) { 

    String INPUT = "testingwithtees"; 
    char C = 't'; 
    int K = 1; 

    int count = subStrMaxC(INPUT, C, K); 
    System.out.println(count); 

} 
public static int subStrMaxC(String s, char c, int k) { 
    char letters[] = s.toCharArray(); 
    int valid = 0; 
    List<Candidate> candidates = new ArrayList<Candidate>(); 
    for (int i=0; i< s.length(); i++) { 
     if (letters[i] == c) 
      candidates.add(new Candidate(k, c)); 

     for (Candidate candidate : candidates) { 
      if (candidate.addLetter(letters[i])) { 
       System.out.println(candidate.value); 
       valid++; 
      } 
     } 

    } 
    return valid; 
    } 
} 

class Candidate { 

final int K; 
final char C; 

public Candidate(int k, char c) { 
    super(); 
    K = k; 
    C = c; 
} 
boolean endsWithC = false; 
String value = ""; 
int kValue = 0; 
public boolean addLetter(char letter) { 
    endsWithC = false; 
    value = value+letter; 
    if (letter == C) { 
     kValue++; 
     endsWithC = true; 
    } 
    return endsWithC && kValue <= K+2 && value.length() > 1; 
} 

} 

Answer 2

О (п) лучший случай, O (п) наихудший случай

Я не уверен, что вы имеете в виду по наименьшей сложности. Если вы говорите о лучшем случае, это будет O (n). (Итерации родительского цикла только и вложенные циклы никогда не итерация), так как согласующий случае:

if(stringChars[i]=='c') 

всегда ложно. Тем не менее, временная сложность , о которой мы обычно говорим, это O (n), поскольку условие if(stringChars[i]=='c') возвращает true каждый раз.