我们知道，给定一个头指针，在单链表上的查找为O（n）。让我们说我一直都在链接列表的一半处保留一个指针。我会改善查找时间吗？
最佳答案
不错的想法，但这仍然不能改善搜索操作。无论列表的不同部分有多少个指针，您仍然必须分析列表中的每个元素。但是，您可能需要两个线程来搜索列表的每一半，从而使该操作在理论上快一倍。
关于c++ - 普通单链表复杂度查询，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9013949/
我们知道，给定一个头指针，在单链表上的查找为O（n）。让我们说我一直都在链接列表的一半处保留一个指针。我会改善查找时间吗？
最佳答案
不错的想法，但这仍然不能改善搜索操作。无论列表的不同部分有多少个指针，您仍然必须分析列表中的每个元素。但是，您可能需要两个线程来搜索列表的每一半，从而使该操作在理论上快一倍。
关于c++ - 普通单链表复杂度查询，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9013949/