runtime - 非单调最坏情况复杂性的示例

Question

有人知道具有非单调最坏情况行为的自然程序或算法吗？

通过非单调最坏情况行为，我的意思是存在一个自然数 n，使得大小为 n+1 的输入的最坏情况运行时间小于大小为 n 的输入的最坏情况运行时间。

当然，很容易构建具有这种行为的程序。自然程序中的小 n（如 n = 1）甚至可能发生这种情况。但我对大 n 非单调的有用算法感兴趣。

Answer 1

想想二分搜索。

在实现二进制搜索时，您需要考虑要拆分的数组段长度为奇数的情况。此时您有 2 个选择： 1. 向上/向下舍入 2. 检查两个索引并在继续之前做出决定。

如果您选择第一种情况（假设您向下取整）。对于您要搜索的数字是通过中间点的数字的奇数长度数组，您将需要进行额外的迭代。
如果那个奇怪的数组再添加一个元素，它会为你节省额外的迭代。

如果您选择第二种情况，那么大多数奇数迭代的算法执行甚至需要更多的比较，然后如果它与一个额外的元素一起使用。

请注意，所有这些都非常依赖于实现，因此如果没有真正的算法（以及真正的实现），就不可能有真正的答案。

此外，所有这些都是基于假设您在谈论实际运行时差异而不是渐近差异。如果不是这种情况，那么答案将是“不”。没有具有非单调最坏情况渐近运行时间的算法。这将违背“最坏情况”的概念。

Answer 2

有人知道具有非单调最坏情况行为的自然程序或算法吗？

请定义“自然程序或算法”。“算法”这个概念有一个我知道的定义，并且肯定有算法（正如你正确承认的那样）具有非单调的最坏情况运行时复杂性。如果一个程序不做不必要的工作或者它所解决的问题类别具有最小的运行时复杂性，它是“自然的”吗？在那种情况下，您会认为 BubbleSort 不是算法吗？更重要的是，我可以定义一个具有非单调最坏情况行为的最有效解决方案的问题。这样的问题会“不自然”吗？你对“自然问题”的定义是什么？

当然，很容易构建具有这种行为的程序。

那么真正的问题是什么？除非您致力于定义自然/有用的算法和问题，否则您的问题没有答案。您是否只对人们已经在现实世界中使用的现有算法感兴趣？如果是这样，您应该说明这一点，问题就变成了搜索文献之一。坦率地说，我无法想象“自然、有用的算法”的合理定义，它会排除许多具有非单调运行时复杂度的算法示例......

但我对大 n 非单调的有用算法感兴趣。

请定义“有用的算法”。“算法”这个概念有一个我知道的定义，并且肯定有算法（正如你正确承认的那样）具有非单调的最坏情况运行时复杂性。如果算法正确解决了某些问题，它是否“有用”？我可以很容易地定义一个可以通过具有非单调运行时复杂度的算法来解决的问题。