4

我们有一个大小为 L 的链表，我们想要检索第 n 个到最后一个元素。

解决方案1：天真的解决方案

  • 从头到尾进行第一次遍历以计算 L
  • 从开始到预期位置进行第二次传球

解决方案2：使用2个指针p1，p2

  • p1 从头开始​​迭代，p2 不动。
  • 当 p1 和 p2 之间有n元素时，p2 也开始迭代
  • 当 p1 到达列表末尾时，p2 处于预期位置

两种解决方案似乎具有相同的时间复杂度（即，2L - n对列表元素的迭代）哪一种更好？

4

4 回答 4

3

这两种算法都是两遍的。对于相当小的 n，第二个可能具有更好的性能，因为第二遍访问已经被第一遍缓存的内存。（通行证是交错的。）

一次性解决方案会将指针存储在循环缓冲区或队列中，并在到达列表末尾时返回队列的“头”。

于 2013-09-16T01:02:43.397 回答
2

如何使用 3 个指针 p、q、r 和一个计数器。

使用 p 更新计数器迭代列表。每 n 个节点将 r 分配给 q，将 q 分配给 p

当您到达列表末尾时，您可以计算出 r 与列表末尾的距离。

您可以在不超过 O(L + n) 的时间内得到答案

于 2013-09-16T01:04:50.427 回答
1

如果n << L，解决方案 2 通常更快，因为缓存，即包含 p1 和 p2 的内存块被复制到 CPU 缓存一次，并且指针在需要再次访问 RAM 之前移动了一堆迭代。

于 2013-09-16T01:02:05.280 回答
0

将链表的长度简单地存储在 O(1) 内存中会不会便宜很多？您必须进行“第一次通过”的唯一原因是因为您不知道链表的长度。如果存储长度，则可以每次迭代 (|L|-n) 个元素并轻松检索元素。对于与 L 相比更高的 n 值，这种方式可以为您节省大量时间。例如，如果 n 等于 |L|，您可以简单地返回列表的头部而根本不进行迭代。

此方法比您的第一个算法使用稍多的内存，因为它将长度存储在内存中，但您的第二个算法使用两个指针，而此方法仅使用一个指针。如果你有第二个指针的内存，你可能有内存来存储链表的长度。

授予 O(|L|-n) 在纯理论中等同于 O(n) ，但是有“快速”线性算法，然后有“慢”算法。这类问题的两遍算法很慢。

正如@HotLicks 在评论中指出的那样，“人们需要了解，在许多情况下，‘大 O’ 复杂性与实际性能仅松散相关，因为它忽略了加法因素和常数乘数。” 在这种情况下，IMO 只是采用最懒惰的方法，不要想太多。

于 2013-09-16T02:42:26.243 回答