当使用的操作有多种可能的算法时，我们如何计算大0 ?

Question

在计算一段代码的大0时，如何处理代码段中使用的操作可能根据所使用的算法具有不同数量的操作的情况?

为了澄清我的问题，我首先要用一个明显愚蠢的例子来清楚地说明问题，然后描述一个更合理但不那么清晰的例子。

非常简单的例子:

假设你想计算

的大0值

import Calculator # Third party library
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

更合理的例子

在机器学习中，有许多不同的第三方库可以帮助加快开发。当我们不知道算法或其中使用的第三方方法的大0时，我们如何确定我们设计的机器学习解决方案的大0 ?

Answer 1

当一个算法的复杂度取决于它的一个(或多个)操作的复杂度，而该操作的复杂度并不一定是已知的，有两种方法可以描述它:

• 给出操作数的复杂度。例如，最优排序算法通常被描述为O(nlogn)时间，但更准确的说法是它们执行O(nlogn)比较操作。比较操作的复杂性通常不取决于列表的长度，但可能以其他方式取决于输入，例如，在最坏的情况下，比较长度c的字符串需要O(c)时间。
• 根据相关操作的复杂性，使用通用术语，如f(n)，而不是使用具体术语，如n^2.373。

将这些选项应用到您的计算器示例中，我们可以说该算法执行O(n)次乘法，或者它的时间复杂度为O(nn)，其中f(n)是乘法的时间复杂度。

Answer 2

问题是如何根据一些样本运行来经验地猜测大0。

答案是把它放在log-log图上。

如果它看起来大致像一条斜率为k的直线，那么它可能有一个大致形式为O(n^k)的大o。这是不精确的，很容易想出反例。但在实践中，它往往很有效。

出问题的主要地方是大0被一个小但快速增长的项所支配。所以在这一项变得足够大之前，它看起来像一个模式，然后它看起来像一个不同的模式。关于一些现实生活中的例子，请参阅accidental Quadratic。