Schleife genau N! mal für die Permutationslogik?

Question

Der folgende Code erhält im Grunde die Permutation einer Zeichenfolge. Also habe ich erwartet, dass die Zeitkomplexität O(N!) ist. Wenn Sie den folgenden Code mit dem Parameter "abc" ausführen, werden die Schleifen 36 statt 3! mal angezeigt, wenn Sie nicht den HashSet verwenden, um zu überprüfen, ob die Zeichenfolge bereits hinzugefügt wurde.

static void Main(string[] args) 
{ 
    generated = new HashSet<string>(); 
    var test = getA(args[0]); 
    int i = 1; 
    foreach (var s in test) 
    { 
     Console.WriteLine($"{i}:{s}"); 
     i++; 
    } 
} 

static HashSet<string> generated; 
private static IEnumerable<string> getA(string v) 
{ 
    if (v.Length <= 1) 
    { 
     yield return v; 
    } 
    else 
    { 
     for (var i = 0; i < v.Length; i++) 
     { 
      var c = v[i]; 
      var s = v.Remove(i, 1); 
      Console.WriteLine($" i:{i} v:{v} c:{c} s:{s}"); 
      foreach (var t in getA(s)) 
      { 
       Console.WriteLine($"  t:{t}"); 
       for (var k = 0; k < t.Length; k++) 
       { 
        if (c != t[k]) 
        { 
         var result = t.Insert(k, c.ToString()); 
         //if (!generated.Contains(result)) 
         { 
          generated.Add(result); 
          yield return result; 
         } 
        } 
       } 
       //if (!generated.Contains(t + c)) 
       { 
        generated.Add(t + c); 
        yield return t + c; 
       } 
      } 
     } 
    } 
} 

Answer 1

Big O bezieht sich auf die asymptotische Komplexität als Variablen ins Unendliche.

Es ist kein Maß für die genaue Nummer von Operationen, die durchgeführt werden.

Wenn Sie die Eingabegröße kontinuierlich erhöhen und näher an Unendlich kommen, nähert sich die tatsächliche Anzahl der ausgeführten Operationen immer mehr dem Wert "N!".