4

语境

我正在实施一项心理测试，向用户呈现成对的图像，并且必须指出他们更喜欢哪一个。他们用 A 或 L 键响应他们的偏好。如果图像的数量很大，那么比较所有可能的对对个体的要求相当高（O(n^2)）。

问题

我在这里破解了合并排序算法，以大大减少比较次数。结果如下：

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}


function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (getUserPreference(left[0],right[0])) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

函数getUserPreference委托给用户的地方。我已经运行了多个模拟（其中响应可能意外地“错误”~1/3 的时间，并且“错误”是指不通过按错误键输入他们的真实偏好）并且根据排序似乎表现良好以下标准：

  • 输出结果足够接近用户偏好（模拟）。
  • 算法适时停止。10 个项目的列表约 20 个步骤。

我想知道的是，那里的算法神童是否可以告诉我该算法是否有可能完全无法停止或逼近输入解决方案。

4

1 回答 1

3

这个算法有没有可能完全无法停止？

不。算法总是停止，无论比较有多么糟糕/错误/不幸。

算法适时停止。10 个项目的列表约 20 个步骤。

对于 10 个项目，最好的情况是 15 次比较，最坏的情况是 25 次比较。通常，归并排序采用平均O(n log n)步数。

该算法是否有可能完全无法逼近输入解决方案

这在很大程度上取决于您对“足够接近用户偏好”的定义。可能一个重要的错误是假设用户偏好是一种传递关系。

于 2016-10-25T16:00:54.740 回答