complexitaet meines C++ algos berechnen

hi,

wie kann ich die komplexitaet folgenden algos berechnen?
die for schleife laeuft wird n-1 mal aufgerufen...
wie kann ich die komplexitaet innerhalb der for schleife berechnen?

The Problem

I call it the "word break" problem and describe it as follows:

Given an input string and a dictionary of words,
segment the input string into a space-separated
sequence of dictionary words if possible. For
example, if the input string is "applepie" and
dictionary contains a standard set of English words,
then we would return the string "apple pie" as output.

string SegmentString(string input, unodered_set<string> dict) {
  if (dict.find(input) != dict.end()) return input;
  int len = input.size();

  for (int i = 1; i < len; i++) {
    string prefix = input.substring(0, i);
    if (dict.find(prefix) != dict.end()) {
      string suffix = input.substring(i, len);
      string segSuffix = SegmentString(suffix, dict);
      if (segSuffix != "") {
        return prefix + " " + segSuffix;
      }
    }
  }
  return string("");
}

Skym0sh0

Bis Zeile 8 hätte ich gesagt das ist was quadratisches. Aber durch den rekursiven Aufruf sieht mir das fast schon nach ner Fakultät aus.

Aber hab nur kurz mit einem Auge drauf geschaut, glaube also selber nicht dran.

Du musst dir eigentlich nur ein paar Fragen selbst beantworten:

Wie teuer ist die Suche in einem unordered_set?
Wie teuer ist substring(0,i) ?
Die for-Schleife läuft nur, solange man noch kein vollständiges Wort vorliegen hat. Wie teuer ist also die for-Schleife ohne den rekursiven Aufruf?
Wie groß ist der Reststring beim rekursiven Aufruf?

Kriegst du alle Fragen beantwortet? Dann hast du auch schon die Gesamtlösung quasi vor dir liegen

@m.e.:

nehmen wir an ich habe die folgende woerter im dictionary:
"a", "aa", "aaa", "aaaa", "aaaaa"
der input string ist "aaaaa" wobei input.size() == len == n

Wie teuer ist die Suche in einem unordered_set?
O(1) wenn es keine Kollisionen gibt
Wie teuer ist substring(0,i)?
O(k) wobei k die laenge des strings ist koennen wir also sagen O(1)
Die for-Schleife läuft nur, solange man noch kein vollständiges Wort
vorliegen hat. Wie teuer ist also die for-Schleife ohne den rekursiven Aufruf?
die for schleife laeft von 1 bis len
ergibt also O(n-1)
Wie groß ist der Reststring beim rekursiven Aufruf?
ich weiss leider nicht wie ich dafuer die komplexitaet berechnen kann...

gutes beispiel um die komplexitaet zu analysieren waere:

Consider a pathological dictionary containing the words
"a", "aa", "aaa", ..., i.e., words composed solely of
the letter 'a'. What happens when the input string is a
sequence of n-1 'a's followed by a 'b'?

hm, kann jemand helfen?