算法导论11.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 561 阅读时长 ≈ 1 分钟

11.1-1

基本思想是从后往前直接查找，找到第一个值就返回当前值。哈希表为空时，将会达到最坏情况。

1
2
3
4
5
DIRECT-ADDRESS-SEARCH(T, m)
  for i = m - 1 downto 0
    if T[i] != NIL
      return i
  return NIL

11.1-2

直接用一个$m$比特数组$T$来表示这个表。如果T[x] == 1，那么$x$在这个表中，否则$x$不在这个表中。

可以发现这些操作都是$O(1)$的时间复杂度。

1
2
3
4
5
6
7
8
BIT-ADDRESS-SEARCH(T, k)
  return T[k]

BIT-ADDRESS-INSERT(T, x)
  T[x] = 1

BIT-ADDRESS-DELETE(T, x)
  T[x] = 0

11.1-3

$m$个槽将不再用于直接存放元素，而是存放对应链表的头节点。那么插入一个元素$x$，相当于在对应的链表T[x.key]上进行操作。

  • INSERT: 在对应的链表上直接以$O(1)$的时间插入元素。

  • DELETE: 在对应的链表上删除元素。基于哈希表的性质，这个链表的长度非常短，可以达到$O(1)$的时间复杂度。

  • SEARCH: 直接将对应链表的表头元素返回即可。如果没有，那么直接返回NIL。整个操作仅需要$O(1)$的时间。

$\star$ 11.1-4

基本思想是，使用一个双向链表$L$来表示这个额外的数据结构，一开始时，这个$L$为空，整个数组并不进行初始化。在整个过程中，$L$中的元素和数组$T$中的元素进行绑定，查找或者删除时会进行绑定校验。因此，每个实体必须再添加一个指针$p$，用来指向$L$中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 链表L是一个双向链表，其中的节点包含前驱指针prev，后继指针next，以及在数组A中的目标下标pos。（这里忽略对数组T进行越界检测）
BIG-ADDRESS-SEARCH(T, k)
  // 判断元素T[k]和L中的节点是否绑定在一起。
  if T[k].p != NIL and T[k].p.pos == k
    return T[k]
  else
    return NIL

BIG-ADDRESS-INSERT(T, L, x)
  k = x.key
  // 这个位置上原来已经包含了一个元素，绑定校验成功。
  if T[k].p != NIL and T[k].p.pos == k
    x.p = T[k].p
    T[k] = x
  else
  // 否则新加入L中。
    let p be new node
    INSERT(L, p)
    T[k] = x
    T[k].p = p
    p.pos = k
    
BIG-ADDRESS-DELETE(T, L, x)
  k = x.key
  // 绑定校验，避免进行非法操作。
  if T[k].p != NIL and T[k].p.pos == k
    DELETE(L, T[k].p)
    T[k].p = NIL

可以发现，每一步的操作无非都是寻址，以及双向链表上的插入和删除操作。因此，这个大哈希表$T$中支持的这三个操作的时间复杂度均为$O(1)$。