根据维基百科：“通常不可能确定确切的最坏情况。相反，一种情况被认为至少与最坏情况一样糟糕”。我不明白那部分。在列表中搜索数字时，最坏的情况不是在最后一个索引处吗？这不是最坏的情况吗？
问问题
210 次
3 回答
5
我想你误读了条目。http://en.wikipedia.org/wiki/Best,_worst_and_average_case
他们说最坏的情况可能是您可以识别的，但确切的输入不是。例如，如果使用桶实现哈希表/字典，很容易说最坏的情况是当所有 100 个样本条目哈希到同一个桶时，但不太容易识别实际哈希到同一个桶的 100 个输入。对于某些算法，几乎不可能得出确切的最坏情况输入数据。
最坏情况分析也有类似的问题：通常不可能确定确切的最坏情况。相反，一个场景被认为至少与最坏的情况一样糟糕。例如，在分析算法时，即使无法确定生成该路径的确切输入，也有可能找到通过算法的最长可能路径（例如，通过考虑最大循环数）（事实上，这样的输入可能不存在）。这给出了一个安全的分析（最坏的情况永远不会被低估），但这是一个悲观的分析，因为可能没有需要这条路径的输入。
于 2012-09-11T19:00:30.857 回答
0
是的，这是您提到的场景的最坏情况，但您提到的场景是一个简单的场景。
想象一棵树上的一个复杂操作，它涉及将节点一直旋转到根。最坏的情况可能是树当前状态的复杂函数。但是更容易想象，例如，您需要进行 O(log(N)) 或 O(N) 旋转，这取决于您是否可以证明其中任何一个都比最坏的情况更糟（当然 O(N) 是在这种更复杂的情况下，最坏的情况是有限的）。
于 2012-09-11T18:59:22.940 回答
0
要计算最坏情况执行时间 (WCET)，您可以根据输入大小考虑每个循环，并假设它不会提前终止。但是，如果您有一个稍微复杂的算法，则可能不会计算导致 WCET 的输入。例如，如果您的算法使用（名称）哈希表，您可以假设所有键都散列到同一个单元格，但您无法判断哪种输入会导致这种情况。尽管甚至可能看到输入语义永远不会导致这样的哈希表，但您仍然会基于所有键具有相同哈希的假设来计算 WCET。
于 2012-09-11T19:06:11.800 回答