英文:
How do we calculate Big O when an operation used has multiple possible algorithms?
问题
计算代码段的大O时，如何处理代码段中使用的操作根据算法的不同可能有不同数量的操作的情况？
为了澄清我的问题，我首先将使用一个非常愚蠢的例子来清楚地展示问题，然后描述一个更为合理但不太清晰的例子。
非常简单的例子：
假设您试图计算以下代码的大O值：
import Calculator # 第三方库
total = 0
b = 7
for a in list_of_As:
total += Calculator.multiply(a, b)
现在我们不知道Calculator.multiply如何计算其结果。
如果Calculator.multiply定义如下，我们的代码可能具有O(n)：
def multiply(a, b):
return a * b
或者如果Calculator.multiply非常低效，定义如下，我们的代码可能具有O(n^2)：
def multiply(a, b):
rtn = 0
for i in range(b):
rtn += a
更为合理的例子：
在机器学习中，有许多不同的第三方库可用于加速开发。当我们不知道其中使用的算法或第三方方法的大O时，如何确定我们设计的机器学习解决方案的大O？
英文:
When calculating the Big O for a section of code how does one handle the situation where an operation used in the code segment could have a different number of operations based on the algorithm used?
To clarify my question I'm first going to use a blatantly stupid example to clearly show the issue and then describe a more reasonable but not as clear example.
Very Simple Example:
Lets say your trying to calculate the Big O value for
import Calculator # Third party library
total = 0
b = 7
for a in list_of_As:
total += Calculator.multiply(a, b)
Now we know nothing about how Calculator.multiply goes about to get its result.
Our code could have O(n) if Calculator.multiply was defined by
def multiply(a, b) :
return a * b
or our code could have O(n^2) if Calculator.multiply was very inefficient and was defined by
def multiply(a, b):
rtn = 0
for i in range(b):
rtn += a
More reasonable example
In machine learning, there are many different third-party libraries available to help speed up development. How does one go about determining the Big O of a machine-learning solution we designed when we don't know the algorithms or the Big O of the third-party methods used within it?
答案1
得分: 3
-
使用算法的复杂度取决于其操作之一（或多个）的复杂度，并且该操作的复杂度不一定已知时，有几种描述它的方式：
-
给出操作数量的复杂度。例如，最佳排序算法通常描述为O(n log n)时间，但更准确的说法是它执行O(n log n)比较操作。比较操作的复杂度通常不取决于列表的长度，但它可能会以某种其他方式取决于输入，例如，在最坏情况下，比较长度为c的字符串需要O(c)时间。
-
使用通用术语，如f(n)来表示相关操作的复杂度，而不是具体术语，如n².373。
将这些选项应用于您的计算器示例，我们可以说算法执行O(n)次乘法，或者它的时间复杂度是O(n f(n))，其中f(n)是乘法的时间复杂度。
英文:
When the complexity of an algorithm depends on the complexity of one (or more) of its operations, and the complexity of that operation is not necessarily known, there are a couple of ways you can describe it:
- Give the complexity of the number of operations. For example, optimal sorting algorithms are often described as O(n log n) time, but it's a little bit more accurate to say that they perform O(n log n) comparison operations. The complexity of a comparison operation typically does not depend on the length of the list, but it may depend on the input in some other way, e.g. it takes O(c) time in the worst case to compare strings of length c.
- Use a generic term such as f(n) for the complexity of the relevant operation, rather than a concrete term such as n<sup>2.373</sup>.
Applying these options to your calculator example, we could say either that the algorithm performs O(n) multiplications, or that its time complexity is O(n f(n)) where f(n) is the time complexity of multiplication.
答案2
得分: 2
问题是如何根据一些样本运行来经验性地猜测大O表示法。
答案是将其放在双对数图上。
如果它看起来大致像一条斜率为k的直线，那么它可能具有大致形式为O(n^k)的大O表示法。这是不精确的，容易找到反例。但在实践中，它通常效果不错。
主要问题在于，大O表示法被一个小但迅速增长的项所主导。所以它看起来像一个模式，直到该项变得足够大，然后它看起来像另一种模式。请参阅Accidentally Quadratic，了解一些实际示例。
英文:
The question is how to empirically guess the big-O based on some sample runs.
The answer is to put it on a log-log plot.
If it looks roughly like a line with slope k, then it probably has a big-O of roughly the form O(n^k). This is imprecise and it is easy to come up with counterexamples. But in practice it tends to work well.
The main thing that goes wrong is that the big-O is dominated by a small but rapidly growing term. So it looks like one pattern until that term becomes big enough, then it looks like a different pattern. See Accidentally Quadratic for a number of real life examples.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论