Java: Wie berechnet man die zeitliche Komplexität eines Programms?

Question

Ich habe folgendes Programm. In einem Fall, wo es mehrere Funktionen hat, kombiniere ich die Zeitkomplexität von jedem oder nehme nur die höchste Zeitkomplexität von allen von ihnen?

Ich glaube, die find() hat eine Zeit Komplexität von n und isCompound hat eine Zeit Komplexität von n hat gut. Ist das korrekt?

Vielen Dank und werde sicher sein, zu stimmen und die Antwort zu akzeptieren.

private static String[] find(String[] array) { 
    Set<String> words = new LinkedHashSet<>(Arrays.asList(array)); 
    Set<String> otherWords = new HashSet<>(words); 
    for (Iterator<String> i = words.iterator(); i.hasNext();) { 
     String next = i.next(); 
     otherWords.remove(next); 
     if (isCompound(next, otherWords)) { 
      i.remove(); 
     } else { 
      otherWords.add(next); 
     } 
    } 
} 

private static boolean isCompound(String string, Set<String> otherWords) { 
    if (otherWords.contains(string)) { 
     return true; 
    } 
    for (String word : otherWords) { 
     if (string.startsWith(word)) { 
      return isCompound(string.replaceAll("^" + word, ""), otherWords); 
     } 
     if (string.endsWith(word)) { 
      return isCompound(string.replaceAll(word + "$", ""), otherWords); 
     } 
    } 
    return false; 
} 

Answer 1

Es gibt nichts wie Zeit Komplexität eines Programms. Wir berechnen Zeitkomplexität für Algorithmen oder im Rahmen der Programmierung für einzelne (atomare) Funktionen.

Wir benchmarken Programme (die aus mehreren Funktionen bestehen können), indem wir ihre Laufzeit in Werkzeugen wie Profilern messen. Stellen Sie sich vor, wenn ein Programm Hunderte von Quelldateien enthält, wie können Sie dann erwarten, dass es seine Zeitkomplexität berechnet?

Um die Komplexität für find und isCompound analysieren wir die Komplexität für die Funktionen in ihnen genannt sicherlich wissen müssen, wie otherWords.remove(next), otherWords.add(next), string.replaceAll("^" + word, "") oder otherWords.contains(string).

Wenn Sie sicher sind, was ihre Komplexität ist, dann können wir die Komplexität für Ihre Funktionen berechnen. Und selbst wenn Sie alle Komplexitäten berechnen, wäre auch das eine Annäherung für sehr große Eingaben. Sie entscheiden also, was Sie wirklich berechnen möchten.

EDIT: Um die Komplexität für Ihr Programm zu berechnen, schlage ich vor, Sie brechen jede der Bibliothek-Funktion, die Sie aufgerufen haben und versuchen, sie zu analysieren. Zum Beispiel, da otherWords ein HashSet ist, können wir daraus schließen, dass otherWords.contains(string) (Nachschlageoperation in einer Hash-Tabelle) O(1) (Big-O) Zeit dauern kann.