如何在偏好算法中实时更新每步的最小/最大比较次数范围？

核心问题分析 #

你当前的calculateMinMax()仅在初始化时计算全量元素的总次数，但每次用户选择后，剩余元素的比较路径会因选择结果不同而变化——比如选择胜者进入下一轮后，后续需要的比较次数取决于当前已确定的偏好关系，而非简单的n-1固定值。

调整后的实现思路 #

1. 跟踪所有已确定的偏好关系：用传递闭包维护直接和间接的胜负关系，避免重复计算可推导的比较。
2. 动态计算剩余次数范围：基于初始总次数，结合已完成的比较次数和传递性节省的次数，实时更新剩余的最小/最大比较次数。
3. 适配你的递归公式：将原公式的初始总次数计算改为迭代求和（避免递归初始化的性能问题），再结合实时状态调整。

TypeScript代码实现 #

class ComparisonApp {
  private items: any[];
  private completedComparisons: number = 0;
  // 传递闭包：key为元素，value为所有被该元素击败的元素（直接+间接）
  private transitiveClosure: Record<string, Set<string>> = {};

  constructor(initialItems: any[]) {
    this.items = [...initialItems];
    // 初始化闭包：每个元素初始无击败对象
    initialItems.forEach(item => {
      this.transitiveClosure[item] = new Set();
    });
  }

  // 计算初始状态下的最小总比较次数（迭代实现原递归公式）
  private getInitialMinTotal(): number {
    let total = 0;
    for (let k = 2; k <= this.items.length; k++) {
      total += Math.floor(Math.log2(k));
    }
    return total;
  }

  // 计算初始状态下的最大总比较次数（迭代实现原递归公式）
  private getInitialMaxTotal(): number {
    let total = 0;
    for (let k = 2; k <= this.items.length; k++) {
      total += Math.ceil(Math.log2(k));
    }
    return total;
  }

  // 更新传递闭包：当winner击败loser时，同步更新所有间接推导关系
  private updateTransitiveClosure(winner: any, loser: any): void {
    // 记录直接胜负
    this.transitiveClosure[winner].add(loser);

    // 所有能击败winner的元素，现在也能击败loser
    Object.keys(this.transitiveClosure).forEach(item => {
      if (this.transitiveClosure[item].has(winner)) {
        this.transitiveClosure[item].add(loser);
      }
    });

    // 所有被loser击败的元素，现在也被winner击败
    this.transitiveClosure[loser].forEach(beatenItem => {
      this.transitiveClosure[winner].add(beatenItem);
    });
  }

  // 计算最优情况下通过传递性节省的比较次数
  private getOptimalSavedCount(): number {
    let totalDetermined = 0;
    this.items.forEach(item => {
      totalDetermined += this.transitiveClosure[item].size;
    });
    // 已完成的比较是直接次数，节省的是间接推导的次数
    return totalDetermined - this.completedComparisons;
  }

  // 用户选择后调用此方法更新进度
  public handleSelection(winner: any, loser: any): void {
    this.completedComparisons += 1;
    this.updateTransitiveClosure(winner, loser);

    const initialMin = this.getInitialMinTotal();
    const initialMax = this.getInitialMaxTotal();
    const optimalSaved = this.getOptimalSavedCount();

    // 剩余最小次数：初始最小总次数 - 已完成次数 - 最优节省次数
    const remainingMin = Math.max(0, initialMin - this.completedComparisons - optimalSaved);
    // 剩余最大次数：初始最大总次数 - 已完成次数（最坏情况无传递性节省）
    const remainingMax = Math.max(0, initialMax - this.completedComparisons);

    // 进度范围计算（已完成次数占总可能次数的比例）
    const progressLower = (this.completedComparisons / (this.completedComparisons + remainingMax)) * 100;
    const progressUpper = (this.completedComparisons / (this.completedComparisons + remainingMin)) * 100;

    // 输出进度信息（可直接用于更新UI进度条）
    console.log(`已完成：${this.completedComparisons}次`);
    console.log(`剩余需要：${remainingMin} ~ ${remainingMax}次`);
    console.log(`进度范围：${progressLower.toFixed(1)}% ~ ${progressUpper.toFixed(1)}%`);
  }
}

// 测试示例：8个水果对比
const fruits = ["苹果", "香蕉", "橙子", "葡萄", "芒果", "草莓", "西瓜", "菠萝"];
const app = new ComparisonApp(fruits);

// 模拟用户选择：苹果击败香蕉
app.handleSelection("苹果", "香蕉");
// 模拟用户选择：苹果击败橙子（此时通过传递性，苹果自动击败香蕉，节省一次间接比较）
app.handleSelection("苹果", "橙子");

关键说明 #

• 传递闭包是动态更新的核心：每次选择后，不仅记录直接胜负，还同步更新所有可推导的间接关系，确保剩余次数计算准确。
• 最小剩余次数对应最优场景：假设所有可通过传递性推导的关系都无需再比较，因此剩余次数最少。
• 最大剩余次数对应最坏场景：假设没有任何传递性节省，所有未直接比较的元素都需要逐一对比，因此剩余次数最多。

内容的提问来源于stack exchange，提问作者Batimius