Wordbreak Zeit Komplexität

Ich studiere mich selbst (dies ist keine Hausaufgabe) und möchte erklären, warum Leute sagen, die Zeit Komplexität dieses Algorithmus ist O (n^2). Für String abcd Beispiel diese Berechnung folgende tunWordbreak Zeit Komplexität

i=0, a 
i=1, ab, a 
i=2, abc, bc, c 
i=3, abcd, bcd, cd, d

und der Gesamtbetrieb 10 kleiner als n ist eine Menge^2 (16, wo n = 4) Kann mir jemand bitte erklären, warum es Komplexität ist O (n^2)?

public boolean wordBreak(String s, List<String> wordDict) { 
     boolean[] dp = new boolean[s.length() + 1]; 
     dp[0] = true; 
     for (int i = 1; i <= s.length(); i++) { 
      for (int j = 0; j < i; j++) { 
       if (dp[j] && wordDict.contains(s.substring(j, i))) { 
        dp[i] = true; 
       } 
      } 
     } 
     return dp[dp.length - 1]; 
    }

Quelle

2017-06-30 codereviewanskquestions

Obwohl die innere Schleife weniger als N mal geschleift ist, nehme an, dass es n/2 ist. Also ist die Gesamtanzahl der Schleife N X N/2, was (NXN)/2 ist, so entfernen wir für die Zeitkomplexität Konstanten, daher ist es O (N2). –

@RohitPadma Sie sollten das als Antwort hinzufügen – samgak

Wenn Sie das nicht als Antwort hinzufügen, werde ich, weil es _exactly_ ist, was ich beantworten würde. –

Auch wenn die innere Schleife weniger als N mal geloopt ist Angenommen, es ist n/2. Also ist die Gesamtzahl der Schleifen N X N/2, was (NXN)/2 ist, so entfernen wir für die Zeitkomplexität Konstanten, daher ist es O (N^2).

Quelle

2017-06-30 05:00:04

Wordbreak Zeit Komplexität

Antwort

Verwandte Themen