最坏情况时间复杂度为O(n)的算法总是比最坏情况时间复杂度为O(n^2)的算法快吗？
共有1个答案
大O表示法没有说明任何给定输入的算法的速度；它描述了时间是如何随着元素的数量而增加的。如果你的算法在恒定的时间内执行，但这个时间是1000亿年，那么对于大范围的输入来说，它肯定比许多线性、二次甚至指数算法慢。
但这可能不是真正的问题。问题是，最坏情况复杂度为O(N)的算法A1是否总是比最坏情况复杂度为O(N^2)的算法A2快；更快地说，它可能指的是复杂性本身。在这种情况下，你只需要一个反例，例如：
- A1具有正常复杂度O（log n）但最坏情况复杂度O(n^2)。
- A2具有正常复杂度O(n)和最坏情况复杂度O(n)。
在本例中，A1通常比A2更快（即缩放更好），尽管它有更大的最坏情况复杂性。
-
null
-
给定一个整数数组arr，计算元素x，使得x 1也在arr中。如果arr中有重复项，请分别计数。 示例1：输入：arr=[1,2,3]输出：2说明：1和2被计数，因为2和3在arr中。 示例2：输入：arr=[1,1,2]输出：2解释：1计数两次，原因2在arr中。 示例3：输入：arr=[1,1,3,3,5,5,7,7]输出：0说明：没有计算数字，因为arr中没有2、4、6或8。 示例4：输入：a
-
查找p的伪码算法为： 假设我有一个int值的数组H[1到m]，其中“p”是峰值元素，如果： 基本上，如果H【p】大于或等于其相邻元素，则H【p】为峰值。 假设数组H在开始和结束时都大于1个元素，数组为H[0到m 1]，其中H[0]=H[m 1]=无穷大。因此，H[0]和H[m 1]是哨兵。然后是元素p，其中1≤ p≤ n、 是一个峰值，如果H【p-1】≤ H【p】≥ H【p 1】。 我认为渐近时间
-
做O（h）算法的时间复杂度是多少？当h是节点的高度，以BST n倍为单位（树中的元素数），我相信是O（n），而不是O（n*h），但我不知道如何证明它。 在O（h）中工作的特定算法是在BST中查找元素的顺序前体。
-
线性搜索所需时间的最坏情况是，该项位于列表/数组的末尾，或者不存在。在这种情况下，算法需要执行比较，以查看每个元素是否为所需值，假设是数组/列表的长度。 根据我对big-O表示法的理解，可以说这个算法的时间复杂度是O（n），因为最坏的情况可能发生，当我们想要保守估计“最坏的情况”时，可以使用big-O。 从堆栈溢出的许多帖子和答案来看，这种想法似乎是有缺陷的，像Big-O符号这样的说法与最坏情况分
-
描述一个O（n logn）-时间算法，给定一组由n个整数和另一个整数x组成的S，该算法确定S中是否存在两个元素，其和正好是x。 我计划用二进制搜索来搜索这个。 我如何找到这个算法的时间复杂度？如果T（n）不是（n log n），正确的算法是什么？