1

我只是在处理 LeetCode 问题，罗马到整数，罗马数字到整数的转换，在完成和比较解决方案之后，我注意到列出的解决方案如何描述它们的计算复杂性有一个相当有趣的细微差别。

我将我的解决方案描述为O(n)与输入元素的数量成线性关系，因为我的解决方案逐个字符地迭代罗马数字的元素。然而，官方解决方案描述了如何使用数字I、V、X、L、C、D和M，只能表示从 1 到 3999 的数字。他们的论点是，因为 Big O 只考虑最坏的情况，而最坏的情况固定在 3999，所以时间复杂度是恒定的O(1)，与过程无关。

这引出了一个非常微妙的问题。当我们说“最坏情况下的性能”时，我们是指在任何给定大小的n情况下，还是在所有n情况下的最坏情况。对于给定n的 ，我们是否考虑最坏情况的性能，或者我们是否考虑n给我们提供全局最坏情况性能的特定选择？

4

1 回答 1

1

一个很好的问题！

好吧，这更像是“跨越所有n”是您问题的答案。

让我们深入研究一下：因为使用罗马数字，我们只能表示最多 3999 的元素。所以，我们可以创建一个程序，超过一定的数字，只会返回“失败”。因此，我们甚至不需要阅读整个字符串来回答我们的问题！我们可以看到，在 Roman to Integer 问题中，我们的运行时间由一些辅音限制，所以我们可以说它是 O(1)。

你对微积分有一些经验吗？因为这实际上就是这样！时间复杂度是您的输入大小接近无穷大时的界限。我们丢弃每个有限数量的“前 n 个案例”，我们只对“大”n 的答案感兴趣。

于 2020-09-15T08:00:32.367 回答