пример наличия O (logn) ^ 2 времени

Question

Привет Есть ли пример для показа некоторого кода, который имеет O (logn) ^ 2. Я не могу получить, где у нас будет такой на этот раз спектакль. спасибо

Answer 1

Я думаю, что это может произойти с вложенными бинарными поисками , которые 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)² сложность.