我刚刚在研究一个LeetCode问题，罗马到整数，罗马数字到整数的转换，在完成并比较解决方案后，我注意到列出的解决方案如何描述其计算复杂性的细微差别。
我把我的解描述为O(n)，与输入元素的数量成线性关系，因为我的解逐个字符地迭代罗马数字的元素。然而，官方的解描述了如何用数字I、V、X、L、C、D和M来表示，只能表示从1到3999的数字。他们的论点是，因为Big O只考虑最坏的情况，而最坏的情况固定在3999，所以无论过程如何，时间复杂度在O(1)都是恒定的。
这引出了一个非常微妙的问题。当我们说"最坏情况性能"时，我们指的是任何给定n大小内的最坏情况，还是在所有n。对于给定的n，我们是否考虑最坏情况的性能，或者我们是否考虑为我们提供全局最坏情况性能的特定n选择？
一个很好的问题！
好吧，这更像是"跨越所有n"是你问题的答案。
让我们深入研究它：因为，对于罗马数字，我们只能表示最多 3999 的元素。 因此，我们可以创建一个程序，超过一定数量，将只返回"失败"。因此，我们甚至不需要阅读整个字符串来回答我们的问题！ 我们可以看到，在罗马到整数问题中，我们的运行时间由一些辅音以上面为界，因此我们可以说它是 O(1(。
你有无穷小微积分的经验吗？ 因为实际上就是这样！ 时间复杂度是输入大小接近无穷大时的界限。 我们丢弃每个有限数量的"前 n 个案例"，我们只对"大"n 的答案感兴趣。