[求助]对搜索紧凑链表的期望时间分析

[wssy]

本题出自算法导论第 10-3 （第三版），主要是为了分析一个随机化搜索过程的期望运行时间。我才疏学浅，有几个点琢磨了好久没弄懂，也没看到靠谱的解释，所以上来问问大家。

题目简介： 假设 n 规模链表使用紧凑链表表示，搜索目标关键字渐进时间通常为 O(n)，但存在算法可实现 O(√n)的期望运行时间。

下图表示一个紧凑链表，三个数组 next/key/prev 长度均为 6，链表有 4 个元素，使用 prev/next 访问前后元素，链表中所有元素总是占据数组的前 n 个位置，这里数组下标从 1 开始，L 表示链表起始元素下标，n 为链表规模，'/' 表示 nil：

| index     | 1      |  2     | 3      |  4     | 5      |  6    |
| --------    | -----   | ----   | -----  | ----    | -----  | ----   |
| next      | 2       |   /    | 1      |   3    |        |        |
| key        | 1      |   6    | 1      |   5    |        |        |
| prev      | 3       |   1    | 4      |   /    |        |        |

这里假设所有关键字互异，链表中元素按照关键字升序排列，k 为目标关键字，L/n 含义同前，算法实现如下：

COMPACT-LIST-SEARCH(L, n, k)

i = L

while i != nil and key[i] < k

    j = RAMDOM(1, n)

        if key[i] < key[j] and key[j] <= k

            i = j

            if key[i] == k

                return i

            i = next[i]

    if i == nil or key[i] > k

        return nil

    else return i

RAMDOM 过程以等概率返回[1, n]中任意数值。

为分析该算法，引入另一个算法 COMPACT-LIST-SEARCH'：

COMPACT-LIST-SEARCH'(L, n, k, t)

    i = L

    for 1 to t

        j = RAMDOM(1, n)

            if key[i] < key[j] and key[j] <= k

                i = j

                if key[i] == k

                    return i

    while i != nil and key[i] < k

        i = next[i]

    if i == nil or key[i] > k

        return nil

    else return i

假设 RANDOM(1, n)返回的随机数序列在这两个算法中相同，并且 COMPACT-LIST-SEARCH 执行时为确定目标关键字，其 while 循环执行了 t 次。

目前可以证明第二个算法为了确定其目标关键字，其 for 和 while 循环一共至少会执行 t 次迭代。

再假设随机变量 Xt 表示第二个算法中 for 循环经过 t 次迭代之后，i 到目标关键字的距离（以需要 next 指针跳转的次数计），还可以说明第二个算法的期望运行时间为 O(t+E[Xt])。

那么，已知 E[Xt] = Pr{Xt >= 1} + Pr{Xt >= 2} + ... + Pr{Xt >= n}，如何证明 E[Xt]<= ((n-1)/n)^t + ((n-2)/n)^t + ... + (1/n)^t ？

另外，大家对 t 和 Xt 是如何定义的？

比如 t 次迭代：1.表示第 t 次迭代中未执行完就返回，或者进入 t+1 次迭代前返回？ 2.第 t+1 次迭代中未执行完就返回？ 类似的 Xt：当目标关键字不存在时仅计算到该关键字的前一个元素还是后一个元素？

谢谢各位了（比心

[wssy]

markdown 语法太恶心了，那个表格我真的尽力了 ( 相信我
顺便求一个自动生成符合 Markdown 语法的文档

[wssy]

@wssy 更正为：顺便求一个自动生成符合 Markdown 语法文档的工具