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