无序数组二分搜索的时间复杂度
我被两个时间复杂性所困扰。使用排序数组进行二分搜索是O（logN）。所以要搜索未排序的数组，我们必须先对其进行排序，使其成为O（NlogN）。然后我们可以执行二分搜索，将复杂度设为O（N），但我听说它可能是O（NlogN）。哪个是正确的？
共有3个答案
线性搜索的时间复杂度为O（n），二进制搜索的时间复杂度为O（log n）（log base-2）。如果我们有一个未排序的数组，并且希望对此使用二进制搜索，那么必须首先对数组进行排序。在这里，我们必须花时间对数组排序，然后花时间搜索元素。
你的问题的答案就在你的问题本身。
您首先对列表进行排序。如果使用快速或合并排序对列表进行排序，复杂性将变为o（n*log n）。第一部分结束。
执行二进制搜索的第二部分是在“排序列表”上完成的。二进制搜索的复杂性是o（log n）。因此，最终程序的复杂性仍然是o（n*log n）。
但是，如果要计算数组的中值，则不必对列表进行排序。一个简单的线性或顺序搜索应用程序可以帮助您做到这一点。
二进制搜索用于“排序”列表。复杂性为O（logn）。
二进制搜索不适用于“未排序”列表。对于这些列表，只需从第一个元素开始直接搜索；这给出了O（n）的复杂性。如果要使用MergeSort或任何其他O（nlogn）算法对数组进行排序，那么复杂性将是O（nlogn）。
O（logn）
-
我已经知道，如果您尝试查找具有特定键的项目，最坏情况下的运行时间是O（n），。如果您试图搜索特定的数据项（您不知道该键），那么最坏情况下的运行时间是O（n）。然而，如果键和数据都是整数，输入项在插入之前被随机置乱，会怎么样。最糟糕的运行时间还会保持不变吗？
-
假设BST的高度是h。如果我们要删除一个有两个子节点的节点，那么该过程的时间复杂度是多少。 我知道在普通的二叉树中，删除的时间复杂度是O（h）；O（n）最坏情况和O（logn）最好情况。但是由于我们用它的右子树的最小节点替换删除节点的键，因此需要更多时间来找到最小键。 那么，有人知道如何解释这种情况下的时间复杂性吗？
-
遍历顶点的每个相邻边的时间复杂度是，例如，，其中是相邻边的数量。因此，对于顶点数，时间复杂度变为=，其中是图中的边总数。既然从队列中移除和添加顶点是，为什么它会作为添加到BFS的总体时间复杂度中？
-
如果二叉树是平衡的，那么二叉搜索的最佳运行时间是O（log（n））。最坏的情况是，如果二叉树非常不平衡，它基本上表示一个链表。在这种情况下，二进制搜索的运行时间将为O（n）。 但是，如果树只是稍微不平衡，就像这棵树的情况一样： 如果我没记错的话，最好的情况仍然是O（log n）。但是最坏的情况是什么？
-
我写了一个函数来寻找目标值在给定数组中应该插入的位置。我们假设数组有不同的值，并按升序排序。我的解必须是O(log N)时间复杂度 此代码的复杂性是否为O（log N）？
-
下面给出了问题陈述和解决方案。我无法理解解决方案背后的逻辑。 问题陈述: 给定一个数组包含n+1个整数，其中每个整数介于1和n之间，证明至少存在一个重复的数字。假设只有一个重复的数字，找到重复的一个。 首先，搜索空间是1到n之间的数字。每次我选择一个数字mid（它是中间的那个），并计算所有等于或小于mid的数字。如果计数大于mid，则搜索空间为[1 mid]，否则为[mid+1n]。我这样做，直到