我正在解决 LeetCode 问题，Roman to Integer ，罗马数字到整数的转换，在完成并比较解决方案之后，我注意到列出的解决方案如何描述其计算复杂性的一个相当有趣的细微差别。
我将我的解决方案描述为 O(n)，与输入元素的数量成线性关系，因为我的解决方案逐个字符地迭代罗马数字的元素。然而，官方解决方案描述了如何使用数字 I、V、X、L、C 、D、M只能表示1～3999的数字。他们的论点是，由于 Big O 只考虑最坏情况，而最坏情况固定为 3999，因此无论进程如何，时间复杂度都恒定为 O(1)。
这引出了一个非常微妙的问题。当我们说“最坏情况性能”时，我们指的是在任何给定大小的n内，还是在所有n中 。对于给定的n，我们是否考虑最坏情况的性能，或者我们是否考虑n的具体选择，给我们>全局最坏情况下的表现？
最佳答案
问得好!
嗯，这更像是“across all n”是你问题的答案。
让我们深入探讨一下:因为使用罗马数字，我们只能表示 3999 以内的元素。 因此，我们可以创建一个程序，超过一定数量后，将仅返回“失败”。因此，我们甚至不需要读取整个字符串来回答我们的问题! 我们可以看到，在罗马到整数问题中，我们的运行时间受到某个辅音的限制，所以我们可以说它是 O(1)。
您有微积分方面的经验吗？因为这实际上就是这样!时间复杂度是输入大小接近无穷大时的界限。我们丢弃每一个有限数量的“前 n 个案例”，并且我们只对“大”n 个的答案感兴趣。
关于big-o - Big O 表示法在计算复杂性方面的细微差别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61960113/