大O表示法的细微差别使计算复杂性 [英] Subtle nuances of Big O notation for computation complexity

问题描述

我只是在处理LeetCode问题，罗马到整数，即转换罗马数字到整数，完成并比较解决方案后，我注意到在列出的解决方案如何描述其计算复杂度方面有一个非常有趣的细微差别.

I was just working on a LeetCode problem, Roman to Integer, the conversion of Roman numerals to integers, and after finishing up and comparing solutions, I noticed a rather interesting nuance in how the solutions listed describe their computational complexity.

我将解决方案描述为 O(n)，它与输入元素的数量呈线性关系，因为我的解决方案是逐个字符地遍历罗马数字的元素.但是，官方解决方案描述了如何使用数字 I ， V ， X ， L 和 C， D 和 M ，只能表示1到3999之间的数字.他们的观点是，由于Big O仅考虑最坏的情况，并且最坏的情况固定为3999，因此时间复杂度恒定为 O(1)，而不考虑进程.

I had described my solution as O(n), linear with the number of input elements, as my solution iterated over the elements of a Roman numeral character by character. The official solutions, however, described how with numerals I, V, X, L, C, D, and M, only numbers from 1 to 3999 can be expressed. Their argument was that because Big O only considers the worst case, and the worst case is fixed at 3999, time complexity is constant at O(1), regardless of process.

这是一个非常微妙的问题.当我们说最坏情况的性能"时，是指在任何给定大小的 n 或所有所有 n 中的范围内的最坏情况.对于给定的 n ，我们是否考虑最坏情况的性能?还是考虑赋予我们的 n 的特定选择?>全球最坏情况下的性能?

This begs a really subtle question. When we say "worst case performance," are we referring to worst case within any given size of n, or across all n. Do we consider, for a given n, the worst case performance, or do we consider the specific choice of n that gives us the global worst case performance?

推荐答案

一个好问题！

好吧，这更像是"n个遍历".

Well, it's more like 'across all n' is the answer to your question.

让我们深入研究吧:因为使用罗马数字，我们最多只能表达3999个元素.因此，我们可以创建一个程序，该程序超过一定数量将仅返回"Failure".因此，我们甚至不需要阅读整个字符串来回答我们的问题！我们可以看到，在从罗马到整数的问题中，我们的运行时间受到一些辅音的限制，因此我们可以说它是O(1).

Lets dive into it: because, with roman numerals, we can only express elements up to 3999. So, we can create a program, that over a certain number, will just return "Failure". thus, we don't need to even read the whole string to answer our question! we can see, that in the Roman to Integer problem, our running time is bounded above by some consonant, so we can say it's O(1).

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

Do you have some experience with infinitesimal calculus? because this is actually just that! the time complexity, is the bound when your input size approach infinity. we discard every finite number of "the first n cases", and we are only interested in the answer for "big" n.

这篇关于大O表示法的细微差别使计算复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！