正好N！時間的排列邏輯？

Question

下面的代碼基本上得到了一個字符串的排列。所以我預計時間複雜度爲O(N!)。 當不使用HashSet來檢查字符串是否已經添加時，運行以下帶參數「abc」的代碼將顯示循環36而不是3!次。

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

大O是指漸進複雜作爲變量趨近於無窮。

這不是測量準確號碼將被執行的操作。

隨着您不斷增加輸入尺寸並使其接近無窮大，實際執行的操作數量將不斷接近「N！」。