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)²复杂。