我们如何减少链接列表中的搜索时间？

我在职业杯上看过这个问题，但没有找到比'SkipList'更好的答案。我在维基百科找到的SkipList的描述很有趣，但是，我不理解“几何/二项分布”等术语......我读了它的内容并深入到概率论中。我只是想实现一种更快速搜索的方法。所以这就是我做的： 1.创建索引。 - 我写了一个函数来创建1000个节点。然后，我创建了一个类型链表的数组，并循环遍历1000个节点，并选取每个第23个元素（我脑海中随机数）并添加到我称之为'index'的数组中。我们如何减少链接列表中的搜索时间？

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为例说明输入元素。我通过'索引'数组并找到索引[i]> 769。因此，现在我将head = index [i-1]和tail = index [i]传递给'find'函数。然后，它将搜索769个短的23个元素。因此，我计算出它总共需要43个跳转（包括数组跳转和node = node.next跳转），以找到我想要的元素，否则它会有采取769跳。

请注意：我认为创建索引数组的代码不是搜索的一部分，因此我不会将时间复杂度（这太可怕了）与'查找'函数的时间复杂度相加。我认为这个索引创建应该在创建列表之后作为一个单独的函数来完成，或者是及时地完成。就像网页在谷歌搜索上显示需要时间。另外，这个问题在微软的一次采访中被问到，我不知道我提供的解决方案是否会有好处，或者我是否会看起来像是一个傻瓜提供这样的解决方案。该解决方案已用Java编写。等待您的反馈。

来源

2013-04-20 Parikksit Bhisay

这个解决方案不可能在面试过程中帮助你，除非你能清楚地解释为什么这个解决方案没有提供任何显着的好处。 – 2013-04-20 20:19:50

所以基本上，这个解决方案没有提供任何重大的好处吗？ – 2013-04-20 20:41:17

很难弄清楚你在这里试图解决什么问题，或者你的解决方案应该如何工作。（提示：完整的工作代码将有助于既！）

然而，有一对夫妇一般的东西，我们可以说：

无法搜索列表数据结构（例如发现在i列表）更好，O(N)除非某种排序已经被放在它上面。例如，对元素进行排序。
如果列表中的元素进行排序，然后将列表是可转位（即获得在i位置的元素是O(1)），那么你可以使用二进制搜索和O(logN)找到的元素。
您无法获取链接列表的位置i处的元素，其效果更好O(N)。

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

来源

2015-11-01 02:04:28

我们如何减少链接列表中的搜索时间？

回答

相关问题