arrays - 识别名人 : how does using a queue save logn questions?

Question

我正在阅读 this paper在“轻微改进”部分的最后，作者说我们可以通过使用队列而不是数组来节省额外的 $log_{2}n$ 个问题。

我不明白这是怎么回事。我和 8 个人在纸上试了一下，无论是使用数组还是队列，在淘汰过程中都提出了相同数量的问题。

下面是数组方法的代码:

procedure Eliminate(V, E)
    L ← MakeList
    for v ∈ V do
        add(L, v)
    while L contains at least two elements do
        u ← Remove(L)
        v ← Remove(L)
        if HasEdge(u, v) then
            Insert(L, v)
        else
            Insert(L, u)
    s ← Remove(L)
    return s

这是队列伪代码

procedure Eliminate(queue)
    while queue.size() >= 1 do
        u ← queue.pop_front()
        v ← queue.pop_front()
        if HasEdge(u, v) then
            queue.push_back(v)
        else
            queue.push_back(u)
    s ← queue.pop_front()
    return s

这里是验证函数

def verify(guests, c):
    for g in guests:
        if HasEdge(c, g) or !HasEdge(g, c):
            return false

请您解释一下这两种方法在执行的比较次数方面有何不同？

Answer 1

你写的方法没有什么不同。你错过了重点。

一个潜在的接收器 v 在 Eliminate 中被调用到 HasEdge 至少 log(n) 次(很容易达到 prof)方法。

问题在于最小化 HasEdge 调用。每个记住调用的潜在接收器的字典将在 Verify 方法中保存对 HasEdge 的 log(n) 调用。

代码可以是这样的:

procedure Eliminate(V, E)
    L ? MakeList
    for v ? V do
        add(L, Tuple(v, new Dictionary<Edge,bool>()))
    while L contains at least two elements do
        u ? Remove(L)
        v ? Remove(L)
        if HasEdge(u[0], v[0]) then
            v[1].add(Edge(u[0], v[0]),true)
            Insert(L, v)
        else
            u[1].add(Edge(u[0], v[0]),false)
            Insert(L, u)
    s ? Remove(L)
    return s

procedure Verify(V, s)
    for v ? V \ {s[0]} do
        if (s[1].Contains(Edge(s[0],v)) then
            if s[0][Edge(s[0],v)]
                return false;
        else
            if HasEdge(s[0], v)
                return false

        if (s[1].Contains(Edge(v,s[0])) then
            if !s[0][Edge(v,s[0])]
                return false;
        else
            if !HasEdge(v,s[0])
                return false
    return true