具有正弦复杂性的算法

Question

我想知道是否存在一种算法，其渐近复杂度以不寻常的方式取决于问题的大小，即不是幂/指数/对数的叠加？例如，像 Θ(n ^ (2 + sin n))?

Answer 1

通常 - 通常您想知道给定输入大小“n”的“最坏可能情况”，然后您可以将其与其他算法及其“最坏可能情况”进行比较，以了解您应该使用什么.

所以最直接的答案是O(n ^ (2 + sin n))可以简单地用计算机作为 - 正弦的最大值(value)是什么 - 它是 1这导致我们O(n ^ (2 + 1)) = O(n^3) ，因此你可以说 n ^ (2 + sin n) = O(n^3) .

---

然而，现实生活比这更复杂。例如 - 快速排序实际上有 O(n^2) , 但在平均情况下它有 O(n*log n) .平均情况很难计算(你必须计算所有排列)

在您的情况下 - 您在 O(n) 之间摆动和 O(n^3) ，所以如果我可以使用你的算法并且还可以使用另一个算法 O(n^2) ，我会在sin n < 0时选择原来的那个在其他情况下 O(n^2)一个