O（logn）^ 2時間のパフォーマンスを持つ例

Question

こんにちは O（logn）^ 2を持つコードを表示する例はありますか。 私はこのようなパフォーマンスをどこに持てるのか分かりません。 ありがとう

Answer 1

これは入れ子になったbinary searchesで起こる可能性があります。これはO(log n)です。ここで

はC＃を使用して、愚かな例です：上記のコードで

public class SuperHeroComparer : IComparer<string> 
{ 
    public int Compare(string first, string second) 
    { 
     int firstLimboIndex = Limbo.BinarySearch(first); 
     int secondLimboIndex = Limbo.BinarySearch(second); 
     if (firstLimboIndex < 0 && secondLimboIndex >= 0) { 
      return 1; 
     if (firstLimboIndex >= 0 && secondLimboIndex < 0) { 
      return -1; 
     return String.Compare(first, second); 
    } 
} 

public static class Continuity 
{ 
    public static int IndexOfSuperHero(string name) 
    { 
     return SuperHeroes.BinarySearch(name, new SuperHeroComparer()); 
    } 
} 

、Continuity.IndexOfSuperHero()はO(log n)²複雑さを持つことになります。