我知道二进制搜索的最佳，平均和最差情况时间复杂度在Best O（1）;平均O（log n）;最糟糕的O（log n）;用于数组实现 . 同样，我知道插入排序的最佳，平均和最差情况时间复杂度为Best O（n）;平均O（n ^ 2）;最差的O（n ^ 2）;用于数组实现 .
但是，我如何解决二元搜索和插入单链表的时间复杂性;双重链表;和循环链表实现？
你只需要一个简单的数组，但不可能有一个列表 . 想想如何在没有遍历中间或从头开始的所有元素的情况下从元素 n/2 传递到 n/4 .
n/2
n/4
另一方面，插入排序是基于连续遍历元素，这在链表中不是问题，因此将保持相同的复杂性 . 请注意，即使您必须从头开始遍历每个元素（如果是单个链接列表），O（N ^ 2）仍然是这种情况，而不是像往常一样向后交换方式 . 阵列 . 然而，它确实需要修改算法，这会向您展示一个非常基础的教训 - 特定算法决定数据结构，使用不同的数据结构通常需要更改算法，在某些情况下 - 也需要复杂性 .
一个简短的答案是查看算法完成的计算机步骤 . 您可能需要查看Algorithm Proofs，以及BigO，Omega和Theta符号 . 不同的算法具有不同的最坏情况和最佳情况 . 给定具有n个给定输入的函数F（n） . 它有G（n）计算机步骤 . 让我们说G（n）= 5x ^ 2 3x 1.大多数人通常会看Big-O.对于Big（O），您可以删除所有系数，然后选择主要的Term . 所以你的Big-O将是x ^ 2
BinarySearch : 需要随机访问元素，你能在喜欢的列表中获取吗？不 . （虽然你可以使用额外的空间将其转换为数组，但这比你必须只使用链表更胜一筹）
Insertion sort :你需要在特定索引之前访问元素，当然你不能在O（1）中为单链表做 .您可以从头开始遍历每个元素的列表，但这会使时间复杂度非常高 .
在双向链表中，您可以轻松应用插入排序，因为您可以在O（1）时间内访问前一个元素 .
在上面的讨论中，您也可以轻松地考虑循环列表 .
希望这可以帮助！
是否可以使用二进制搜索取决于您是否可以随机访问项目（即按索引访问项目） . 你永远不能从列表中访问项目（单链表;双重链表;和循环链表（）通过索引，所以你不能在列表上实现二进制搜索 . 但是，您可以改用Skip List . 您可以在跳过列表中获得O（1）（最佳情况）O（lnN）（平均值和最差值）搜索 .
因为，您不需要在插入排序中按索引访问，所以插入排序的数组和列表之间没有区别 . 通常，您需要访问上一个项目以插入当前项目，但是，您也可以按相反的顺序对项目进行排序，并从头开始查找位置（即列表的头部）并最后反转列表 . 它不会改变时间复杂性 .
4 回答
你只需要一个简单的数组，但不可能有一个列表 . 想想如何在没有遍历中间或从头开始的所有元素的情况下从元素
n/2传递到n/4.另一方面，插入排序是基于连续遍历元素，这在链表中不是问题，因此将保持相同的复杂性 . 请注意，即使您必须从头开始遍历每个元素（如果是单个链接列表），O（N ^ 2）仍然是这种情况，而不是像往常一样向后交换方式 . 阵列 . 然而，它确实需要修改算法，这会向您展示一个非常基础的教训 - 特定算法决定数据结构，使用不同的数据结构通常需要更改算法，在某些情况下 - 也需要复杂性 .
一个简短的答案是查看算法完成的计算机步骤 . 您可能需要查看Algorithm Proofs，以及BigO，Omega和Theta符号 . 不同的算法具有不同的最坏情况和最佳情况 . 给定具有n个给定输入的函数F（n） . 它有G（n）计算机步骤 . 让我们说G（n）= 5x ^ 2 3x 1.大多数人通常会看Big-O.对于Big（O），您可以删除所有系数，然后选择主要的Term . 所以你的Big-O将是x ^ 2
BinarySearch : 需要随机访问元素，你能在喜欢的列表中获取吗？不 . （虽然你可以使用额外的空间将其转换为数组，但这比你必须只使用链表更胜一筹）
Insertion sort :
你需要在特定索引之前访问元素，当然你不能在O（1）中为单链表做 .
您可以从头开始遍历每个元素的列表，但这会使时间复杂度非常高 .
在双向链表中，您可以轻松应用插入排序，因为您可以在O（1）时间内访问前一个元素 .
在上面的讨论中，您也可以轻松地考虑循环列表 .
希望这可以帮助！
是否可以使用二进制搜索取决于您是否可以随机访问项目（即按索引访问项目） . 你永远不能从列表中访问项目（单链表;双重链表;和循环链表（）通过索引，所以你不能在列表上实现二进制搜索 . 但是，您可以改用Skip List . 您可以在跳过列表中获得O（1）（最佳情况）O（lnN）（平均值和最差值）搜索 .
因为，您不需要在插入排序中按索引访问，所以插入排序的数组和列表之间没有区别 . 通常，您需要访问上一个项目以插入当前项目，但是，您也可以按相反的顺序对项目进行排序，并从头开始查找位置（即列表的头部）并最后反转列表 . 它不会改变时间复杂性 .