给定概率界限的大 O 符号？
Big O-notation given probabalistic bounds?
我正在尝试估算以下算法的运行时复杂度：
for i in range(0, len(arr)):
for j in range(i+1, len(arr)):
if distance(arr[i], arr[j]) > 2:
pass
距离函数的复杂度是min(len(arg1), len(arg2))。理论上arguments的最大长度可以达到N，但在实践中通常注意超过N的20%。
据此，我可以估计运行时函数为：
f(N) = N*(N/2)*(N*.2)
大O表示法是O(N^2)还是O(N^3)？如果是 O(n^3)，那么在实践中如何证明运行时间总是更接近 O(n^2) 而不是 O(n^3)？
谢谢
还是O(n^3)。人们可能会认为 O(0.0000001 * n^3) 是 "better" 而不是 O(n^2)。但是，如果我们讨论算法的理论复杂性，那么只需假设 n 可以和 10^100 一样大，您将始终理解 O(n^3) 是 "worse"性能。
令len(arr) = N.
由于原始语句在第二个循环中，让我们看看它执行了多少次运行。
内循环运行s
第一次N-1次
第二次N-2次
第三次N-3次
...
...
...
1 次第 (N-1) 次。
显然总和为 = (N-1)(N)/2 = X（比方说）。距离函数被执行X次，在渐近分析中，我们考虑最坏的情况，这意味着距离函数的复杂度是= O( N).
因此 T(N) = ((N-1)(N)/2)N = Y(比方说)
使用 Big O
的定义
Y <= c(N^3), 对于所有 n >= 1，并且 c = 1.
因此 T(N) = O(N^3)
你问：
If it's O(n^3), then how does one justify that the runtime is always going to be closer to O(n^2) than to O(n^3) in practice?
答案是"closer"无所谓。只有 "bigger than" 和 "smaller than" 重要。
大O给出了一个上限
如果一个过程的运行时复杂度最终超过 c * n^2 对于任何常量 c 或更大以及足够大的值 n，那么它不可能是 O(n^2)。
那是因为 big-O 运算符没有给出 估计值；它给出了一个 上限 。即使在恒定时间内运行的过程仍然是 O(n^3)。 （它也是 O(n^2)、O(log(n))、O(n!) 等等）。那是因为对于某些常量乘数 c 和较大的 n 值，它比所有这些运行时间都小。
一个具体的例子
要具体化，请考虑以下事项：
>>> def fa(n):
... return n * n * n // 10
...
>>> def f2(n):
... return n * n
...
>>> def f3(n):
... return n * n * n
...
对于上述运行时间和小n，fa仍然小于或等于f2：
>>> fa(10), f2(10), f3(10)
(100, 100, 1000)
但是如果我们将 n 乘以 10，fa 就会超过 f2。
>>> fa(100), f2(100), f3(100)
(100000, 10000, 1000000)
不难看出，即使我们将 f2 提升一个常量乘数 c，我们仍然可以找到 n 的值，使得 fa(n)更大。
>>> def f2_boost(n, c):
... return f2(n) * c
...
>>> fa(1000), f2_boost(1000, 10), f3(1000)
(100000000, 10000000, 1000000000)
为什么要使用常量乘数？
您可能仍然会感到困惑，因为运行时间为 n^3 * 0.1 的过程与运行时间为 1000 * n^3 的过程属于同一大 O 类别。毕竟，这两个运行时的绝对差异是巨大的！
这有点难以解释，但当您提醒自己大 O 符号应该描述 缩放 行为时，它就开始有意义了。或者，换句话说，大 O 表示法应该描述当我们更改用于测量的 单位 的大小时运行时如何变化。
让我们举一个具体的例子：假设您想知道建筑物的高度。假设有人说 "oh, it's about 300 meters." 你可能会对那个回答感到满意；你可能不在乎它真的是 315 米； 300是一个足够好的估计。但是，如果相反，他们说 "oh, it's about 300 meters... or was that 300 feet?" 你可能会感到不那么满意，因为 300 米是 300 英尺的三倍多。
在计算机科学中，我们在测量时间时遇到了这个问题。事实上，情况更糟。不同的计算机可能比其他计算机快得多或慢得多。如果我们以 "number of calculations performed by a computer," 为单位测量时间，那么对于某些计算机，我们将以百分之一秒为单位测量时间，而对于其他计算机，我们将以 十亿分之一 为单位测量时间第二。如果我们想以一种不会因巨大差异而扭曲的方式来描述算法的行为，那么我们需要一个 "scale invariant" 的度量——也就是说，无论我们使用百分之一秒或十亿分之一秒作为我们的单位。
大 O 符号提供了这样的度量。它为我们提供了一种测量运行时间的方法，而无需太担心我们用来测量时间的单位的大小。本质上，说一个算法是 O(n^2) 是说对于等于或大于某个值 c 的任何时间单位，n 都有一个对应的值，这样我们的过程将在 c * n^2 之前完成对于所有较大的 n 值。
估计 运行时间
如果您想谈论 估计 运行时间，那么您需要一个名为 "big theta." 的测量，请查看 this answer 了解详细信息。简而言之，大O给出了任意大乘数c的上限； big omega 给出了任意大的乘数 c 的 下限 ； big theta 给出了一个定义上限和下限的函数，具体取决于乘数 c 的选择。
在您的情况下，大的 theta 值将是 O(n^3)，因为您可以选择常数乘数 c1，使得 c1 * n^3 始终大于 n^3 / 10，并且您可以选择常数乘数 c2，使得 c2 * n^3 始终小于 n^3 / 10。
我正在尝试估算以下算法的运行时复杂度：
for i in range(0, len(arr)):
for j in range(i+1, len(arr)):
if distance(arr[i], arr[j]) > 2:
pass
距离函数的复杂度是min(len(arg1), len(arg2))。理论上arguments的最大长度可以达到N，但在实践中通常注意超过N的20%。
据此，我可以估计运行时函数为：
f(N) = N*(N/2)*(N*.2)
大O表示法是O(N^2)还是O(N^3)？如果是 O(n^3)，那么在实践中如何证明运行时间总是更接近 O(n^2) 而不是 O(n^3)？
谢谢
还是O(n^3)。人们可能会认为 O(0.0000001 * n^3) 是 "better" 而不是 O(n^2)。但是，如果我们讨论算法的理论复杂性，那么只需假设 n 可以和 10^100 一样大，您将始终理解 O(n^3) 是 "worse"性能。
令len(arr) = N.
由于原始语句在第二个循环中，让我们看看它执行了多少次运行。
内循环运行s
第一次N-1次
第二次N-2次
第三次N-3次
... ... ...
1 次第 (N-1) 次。
显然总和为 = (N-1)(N)/2 = X（比方说）。距离函数被执行X次，在渐近分析中，我们考虑最坏的情况，这意味着距离函数的复杂度是= O( N).
因此 T(N) = ((N-1)(N)/2)N = Y(比方说)
使用 Big O
的定义Y <= c(N^3), 对于所有 n >= 1，并且 c = 1.
因此 T(N) = O(N^3)
你问：
If it's O(n^3), then how does one justify that the runtime is always going to be closer to O(n^2) than to O(n^3) in practice?
答案是"closer"无所谓。只有 "bigger than" 和 "smaller than" 重要。
大O给出了一个上限
如果一个过程的运行时复杂度最终超过 c * n^2 对于任何常量 c 或更大以及足够大的值 n，那么它不可能是 O(n^2)。
那是因为 big-O 运算符没有给出 估计值；它给出了一个 上限 。即使在恒定时间内运行的过程仍然是 O(n^3)。 （它也是 O(n^2)、O(log(n))、O(n!) 等等）。那是因为对于某些常量乘数 c 和较大的 n 值，它比所有这些运行时间都小。
一个具体的例子
要具体化，请考虑以下事项：
>>> def fa(n):
... return n * n * n // 10
...
>>> def f2(n):
... return n * n
...
>>> def f3(n):
... return n * n * n
...
对于上述运行时间和小n，fa仍然小于或等于f2：
>>> fa(10), f2(10), f3(10)
(100, 100, 1000)
但是如果我们将 n 乘以 10，fa 就会超过 f2。
>>> fa(100), f2(100), f3(100)
(100000, 10000, 1000000)
不难看出，即使我们将 f2 提升一个常量乘数 c，我们仍然可以找到 n 的值，使得 fa(n)更大。
>>> def f2_boost(n, c):
... return f2(n) * c
...
>>> fa(1000), f2_boost(1000, 10), f3(1000)
(100000000, 10000000, 1000000000)
为什么要使用常量乘数？
您可能仍然会感到困惑，因为运行时间为 n^3 * 0.1 的过程与运行时间为 1000 * n^3 的过程属于同一大 O 类别。毕竟，这两个运行时的绝对差异是巨大的！
这有点难以解释，但当您提醒自己大 O 符号应该描述 缩放 行为时，它就开始有意义了。或者，换句话说，大 O 表示法应该描述当我们更改用于测量的 单位 的大小时运行时如何变化。
让我们举一个具体的例子：假设您想知道建筑物的高度。假设有人说 "oh, it's about 300 meters." 你可能会对那个回答感到满意；你可能不在乎它真的是 315 米； 300是一个足够好的估计。但是，如果相反，他们说 "oh, it's about 300 meters... or was that 300 feet?" 你可能会感到不那么满意，因为 300 米是 300 英尺的三倍多。
在计算机科学中，我们在测量时间时遇到了这个问题。事实上，情况更糟。不同的计算机可能比其他计算机快得多或慢得多。如果我们以 "number of calculations performed by a computer," 为单位测量时间，那么对于某些计算机，我们将以百分之一秒为单位测量时间，而对于其他计算机，我们将以 十亿分之一 为单位测量时间第二。如果我们想以一种不会因巨大差异而扭曲的方式来描述算法的行为，那么我们需要一个 "scale invariant" 的度量——也就是说，无论我们使用百分之一秒或十亿分之一秒作为我们的单位。
大 O 符号提供了这样的度量。它为我们提供了一种测量运行时间的方法，而无需太担心我们用来测量时间的单位的大小。本质上，说一个算法是 O(n^2) 是说对于等于或大于某个值 c 的任何时间单位，n 都有一个对应的值，这样我们的过程将在 c * n^2 之前完成对于所有较大的 n 值。
估计 运行时间
如果您想谈论 估计 运行时间，那么您需要一个名为 "big theta." 的测量，请查看 this answer 了解详细信息。简而言之，大O给出了任意大乘数c的上限； big omega 给出了任意大的乘数 c 的 下限 ； big theta 给出了一个定义上限和下限的函数，具体取决于乘数 c 的选择。
在您的情况下，大的 theta 值将是 O(n^3)，因为您可以选择常数乘数 c1，使得 c1 * n^3 始终大于 n^3 / 10，并且您可以选择常数乘数 c2，使得 c2 * n^3 始终小于 n^3 / 10。