仍然不理解Big-O vs最坏情况时间复杂性
线性搜索所需时间的最坏情况是，该项位于列表/数组的末尾，或者不存在。在这种情况下，算法需要执行n比较，以查看每个元素是否为所需值，假设n是数组/列表的长度。
根据我对big-O表示法的理解，可以说这个算法的时间复杂度是O（n），因为最坏的情况可能发生，当我们想要保守估计“最坏的情况”时，可以使用big-O。
从堆栈溢出的许多帖子和答案来看，这种想法似乎是有缺陷的，像Big-O符号这样的说法与最坏情况分析无关。
请帮助我理解这种区别，不要让我感到困惑，因为这里的答案是：为什么big Oh不总是算法的最坏情况分析？做
我不认为big-O与最坏情况分析无关。从我目前的山顶来看，big-O似乎表达了最坏情况是如何随着输入大小的增长而增长的，这似乎与最坏情况分析非常“相关”。
像这样的声明，来自https://medium.com/omarelgabrys-blog/the-big-scary-o-notation-ce9352d827ce :
例如，最坏情况分析给出了假设输入处于最坏状态的最大操作数，而大o表示法表示在最坏情况下完成的最大操作数。
没什么帮助，因为我看不出有什么区别。
任何增加的清晰度非常感谢。
共有2个答案
情况是这样的：
如果一个寻找问题解决方案的算法在O（f（n））中，意味着通过该算法寻找问题解决方案的最坏情况是在O（f（n））中。换句话说，如果最坏的情况可以通过算法在g（n）步骤中找到，那么g（n）在O（f（n））中。
例如，对于搜索算法，正如您所提到的，我们知道最坏的情况可以在O（n）中找到。现在，虽然算法在O（n）中，但我们可以说算法也在O（n^2）中。正如你所见，这里是大Oh复杂性和最坏情况之间的区别。
总之，算法的最坏情况场景复杂度是算法的大哦复杂度的子集。
big-O符号确实独立于最坏情况分析。它适用于任何你想要的功能。
在线性搜索的情况下，
>
最坏情况下的复杂度是O（n）（实际上甚至是Θ（n）），
平均情况复杂度为O（n）（实际上偶数Θ（n）），
最好的情况复杂度是O（1）（实际上甚至是Θ（1））。
所以大O和最坏情况是不同的概念，尽管算法运行时间的大O界必须适用于最坏情况。
-
我想展示Quicksort空间复杂性的最坏情况。 我在想它，快速排序不使用辅助数组，它只是在分区子程序上创建一些辅助变量，但它只是操作数组中的项目。所以，很明显，我的结论是它使用了O（n）空间。 但我在网上搜索发现，Quicksort在最坏情况下的空间复杂度为O（logn）。 我只是不明白为什么在最坏的情况下，它比输入数组占用的空间更少？ ps：我在看《算法导论》这本书。 我已经尝试的是计算算法中
-
null
-
由于splay树是一种不平衡的二元搜索树（brilliant.org/wiki/splay树），它不能保证最大高度为O（log（n））。因此，我认为它不能保证最坏情况下的搜索时间为O（log（n））。 但根据bigocheatsheet。通用域名格式： Splay树的最坏情况搜索时间为O（log（n））？？？
-
我被许多声称渐近符号与最好情况、一般情况和最坏情况的时间复杂度无关的说法搞糊涂了。如果是这种情况，那么下面的组合可能都是有效的: 最佳情况 - 最佳情况输入的上限 为了尽可能好的输入，该算法执行的基本操作的数量永远不会超过n的某个常数倍。 对于平均输入，该算法执行的基本操作的数量永远不会超过n的某个常数倍。 对于最坏的可能输入，该算法执行的基本操作的数量永远不会超过n的某个常数倍。 为了获得最佳输
-
因为最坏情况下的快速排序复杂度为O（n^2） 在递增顺序的情况下，当pivot选择第一个或最后一个元素时，它给出了正确的最坏情况复杂度O（n^2），因为树的一个子元素总是空的 但是当枢轴选择中间时，我感到困惑？它将树分成两半，使其复杂性O（n.logn） 假设10 20 30 40 50 60 70枢轴=40 (10 20 30 ) 40 (50 60 70) 左侧枢轴20，右侧枢轴60 (10)