Как сделать кендаллс тау за O (n log n)? O (n ^ 2) отображается

Я пытаюсь написать метод, который будет рассчитывать kendalls tau за время O (n log n). Мне удалось это сделать в O (n ^ 2) довольно легко, однако я не могу найти в Интернете какого-либо ХОРОШЕГО объяснения, которое с легкостью описывало бы, как его кодировать в более быстрой временной сложности?

Вот несколько ссылок на упоминание того, как модифицированная сортировка слиянием или пузырьковая сортировка могут помочь в вычислении рангов для каждой точки x, y для kendalls tau, но все, что они упоминают, это то, что вы можете получить количество обменов, сделанных в качестве возврата, и идти. оттуда? тогда что? википедия переполнение стека

Вот мой код в O (n ^ 2). Довольно, пожалуйста, объясните мне, как это сделать, используя модифицированную сортировку слияния / пузырьков в O (n log n)?

using System.Linq;
using System;

class Kendall
{
    public static double Compute(double[] Xs, double[] Ys)
    {
        XYPoint[] ByX = new double[Xs.Length];
        ByX = sortByX(Xs, Ys);
        double concordant = 0;
        double discordant = 0;
        for (int i = 0; i< ByX.Count; i++)
        {     
            for(int j = i+1; j < ByX.Count; j++)
            {
                if(ByX[j].Y < ByX[i].Y)
                {
                    discordant += 1;
                }

                if(ByX[j].Y > ByX[i].Y)
                {
                    concordant += 1;
                }
            }
        }

        double kendall = (concordant - discordant) / (concordant + discordant);
        return kendall;
    }

    public static XYPoint[] sortByX(double[] Xs, double[] Ys)
    {
        XYPoint[] XYPoints = new XYPoint[Xs.Length]();

        for(int i = 0;  i<Xs.Length; i++)
        {
            Xs[i] = new XYPoint(){X = Xs[i], Y = Ys[i]};
        }

        XYPoint[] ByX = new XYPoint[Xs.Length];
        ByX = XYPoints.OrderBy(z => z.X).ToArray();

        return ByX;
    }

}

public class XYPoint
{
    public double X;
    public double Y;
}

РЕДАКТИРОВАТЬ: Вот код github, который я обнаружил, который реализует этот модифицированный алгоритм сортировки, который возвращает инверсии. Как бы отсюда уйти? github

0

Добавить комментарий

Ваш адрес email не будет опубликован.