java - 如何减少链表中的搜索时间？

Question

我在职业杯上读到了这个问题，但除了“SkipList”之外没有找到任何好的答案。我在维基百科上找到的 SkipList 的描述很有趣，但是，我不理解一些术语，例如“几何/二项式分布”...我阅读了它是什么并深入研究了概率理论。我只是想实现一种方法来加快搜索速度。这就是我所做的:1. 创建索引。- 我编写了一个函数来创建 1000 个节点。然后，我创建了一个链表类型的数组，循环遍历 1000 个节点，并选取每 23 个元素(我想到的随机数)并将其添加到我称之为“索引”的数组中。

    SLL index = new SLL[50]

现在创建索引的函数:

    private static void createIndex(SLL[] index, SLL head){
    int count=0;
    SLL temp = head;
    while(temp!=null)
    {
        count++;
        temp = temp.next;
        if((count==23){
            index[i] = temp;
            i++;
            count=0;
        }
    }       
}

现在终于有了“查找”功能。在该函数中，我首先以输入元素 769 为例。我浏览“index”数组并找到index[i]>769。因此，现在我将 head = index[i-1] 和 tail = index[i] 传递给“find”函数。然后它将在 23 个元素的短范围内搜索 769 个。因此，我计算出总共需要 43 次跳转(包括数组跳转和 node=node.next 跳转)才能找到我想要的元素，否则会出现进行了 769 次跳跃。

请注意:我认为创建索引数组的代码不是搜索的一部分，因此我不会将其时间复杂度(这很糟糕)与“查找”函数的时间复杂度相加。我认为索引的创建应该在创建列表后作为单独的函数完成，或者及时进行。就像网页需要时间才能出现在谷歌搜索中一样。另外，这个问题是在微软面试中被问到的，我想知道我提供的解决方案是否有什么好处，或者我提供这样的解决方案看起来像个傻瓜。该解决方案是用 Java 编写的。等待您的反馈。

Answer 1

很难弄清楚您在这里试图解决什么问题，或者您的解决方案应该如何工作。 (提示:完整的工作代码对两者都有帮助!)

但是我们可以说一些一般性的事情:

• 您无法以 O(N) 更好的方式搜索列表数据结构(例如，在列表中查找 i)，除非某种排序具有被放置在其上。例如，对元素进行排序。

• 如果列表的元素已排序并且列表可索引(即获取位置 i 处的元素是 O(1))，那么您可以使用二分查找并在 O(logN) 中查找元素。

• 您无法以 O(N) 更好的方式获取链表中位置 i 的元素。

如果您添加辅助数据(索引等)，您可能会为某些操作获得更好的性能......但代价是更多的存储空间，并使某些其他操作更加昂贵。但是，您不再拥有列表/链接列表。整个数据结构是“别的东西”。