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)²複雜。